C++实现简单的内存碎片统计 _ 空闲链表遍历算法【源码】

C++实现简单的内存碎片统计：空闲链表遍历算法【源码】

怎么用 C++ 模拟空闲链表并统计内存碎片

开门见山，先说结论：统计内存碎片，其实不必大动干戈去重写 malloc。一个更直接的思路是，用自定义的 std::list 配合一个固定大小的内存池，就能把这事儿给办了。核心在于，我们把“空闲块”抽象成一个包含起始地址 addr 和大小 size 的结构体节点，然后按地址升序排列。接下来，遍历这个有序链表，相邻块之间的地址间隙就是外部碎片，而单个块里因为分配请求被“切”下来、却又小到无法再次利用的“边角料”，就是内部碎片。

这里有个常见的理解误区：别以为空闲的小块数量多就是碎片严重。关键得看它们能不能拼凑出你想要的尺寸。举个例子，就算你有10个64字节的空闲块，但如果程序需要分配一个512字节的连续内存，而它们地址不连续，那这些小块依然是碎片，帮不上忙。

具体怎么搭建呢？可以遵循这几个步骤：

• 首先，用一个大数组来模拟堆内存，比如 char heap[1024 * 1024]，这就是我们1MB的“沙盘”。
• 接着，维护一个 std::list，其中 FreeBlock 结构体包含 void* addr 和 size_t size。
• 初始化时，把整个堆作为一个大空闲块插入链表，地址指向 heap，大小就是整个数组的尺寸。
• 每次分配内存时，从链表中按策略（比如首次适配或最佳适配）找到合适的块，进行拆分，并更新链表。
• 释放内存时，则要检查并合并地址相邻的空闲块，确保链表能真实反映连续的空闲区域。

结论：用自定义std::list（按地址升序维护）+ 固定大小内存池即可模拟空闲链表并统计碎片；外部碎片通过遍历相邻空闲块计算地址间隙，内部碎片统计拆分后不可用的残余块（size < MIN_ALLOC_SIZE）。

如何识别和量化外部碎片（gap-based fragmentation）

外部碎片，说白了就是空闲块之间那些“看得见却用不上”的地址间隙。这些间隙本身并不存储在空闲链表里，必须通过遍历按地址排序后的链表，才能推算出来。

这里有个关键前提：你的空闲链表必须严格按照 addr 升序排列，否则间隙（gap）根本算不准。实现时，别图省事用 std::vector 存了再每次排序——插入删除的开销太大。更优的选择是使用 std::list 并在插入时手动维护顺序，或者直接用 std::set 来自动排序。

那么，具体怎么计算呢？

• 遍历这个有序的空闲块列表，对于每一对相邻的节点 a 和 b，计算 gap = b.addr - (a.addr + a.size)。
• 如果 gap > 0，那就意味着存在外部碎片，把这个 gap 值累加到总的外部碎片字节数里。
• 还可以进一步细化统计，比如记录下 gap < 16 字节的微小间隙数量，这种尺寸通常什么也分配不了，是纯粹的浪费。
• 需要注意，计算范围仅限于堆内：第一个空闲块之前和最后一个空闲块之后的地址空间，不属于可用堆内存，不应计入 gap。

立即学习“C++免费学习笔记（深入）”；

内部碎片统计不能只看 malloc 对齐

内部碎片指的是已经分配出去的内存块中，没有被实际用到的部分。它通常源于内存对齐的要求，或者系统的最小分配单元限制。但在我们自定义的内存池场景里，内部碎片更常出现在两种情况下：一是拆分空闲块时因尺寸取整产生的“零头”；二是用户请求的大小与空闲块尺寸不完全匹配，切分后剩下的“边角料”。

举个例子：一个1024字节的空闲块，用户申请1000字节。按需分配后，会剩下24字节。如果这24字节小于我们设定的最小分配粒度（比如16字节），那么它就会被挂回空闲链表，但后续几乎不可能被再次利用——这就成了实质上的内部碎片。

统计时需要把握几个要点：

• 每次从一个空闲块 f 中分配 req_size 大小的内存时，差值 f.size - req_size 只是潜在的内部碎片。
• 真正应该计入统计的，是拆分后新生成并加入空闲链表的那个“残余块”，并且其 size 必须小于预设的 MIN_ALLOC_SIZE（例如8或16字节）。
• 要避免重复统计。同一个空闲块经过多次拆分，只对最终产生的、不可用的尾部残余进行计数。
• 别简单地套用 sizeof(size_t) 或 alignof(max_align_t) 来计算对齐开销。在你的池子里，对齐策略由你定义。比如你规定所有分配按16字节对齐，并在每块头部预留16字节存放元数据，那么这部分开销也属于内部碎片，需要纳入考量。

为什么 std::list 遍历比 vector 快，但合并操作容易出错

选择 std::list 的原因很直观：作为双向链表，它的插入和删除操作时间复杂度是 O(1)，要维持地址有序，只需找到正确位置后进行拼接（splice）即可。相比之下，std::vector 每次插入都可能涉及大量元素的移动（memmove），是 O(n) 的操作。然而，std::list 的“坑”往往出现在合并空闲块的逻辑上。

合并操作不仅仅是删除节点那么简单。假设有三个连续的空闲块 A、B、C，如果先合并了 A 和 B，但没处理好指针，可能就会漏掉 B 和 C 的合并机会，导致链表状态错误。

正确的合并姿势应该是这样的：

• 释放内存时，首先查找前驱：是否存在一个块 p，满足 p.addr + p.size == freed_block.addr（即前一个块的尾部紧挨着当前释放块的头部）。
• 然后查找后继：是否存在一个块 n，满足 freed_block.addr + freed_block.size == n.addr（即当前释放块的尾部紧挨着后一个块的头部）。
• 合并的顺序很重要：必须先和前驱块合并（合并后会形成一个新的、地址更大的块），再用这个新块的地址去判断是否能和后继块合并。
• 注意迭代器失效问题：使用 std::list::erase() 删除节点后，指向该节点的迭代器会立即失效。不要在循环中直接使用它来访问下一个元素，正确的做法是在删除前，先用 std::next(it) 或提前保存下一个迭代器。
• 调试利器：写一个 dump_freelist() 函数，打印链表中每个块的 addr 和 size。很多时候，肉眼扫一遍输出，就能立刻发现地址断裂或者块重叠的问题。

最后提醒两个容易忽略的细节：第一，碎片统计一定要在所有分配和释放操作完成之后的“稳定状态”下进行，中间过程的临时碎片数据没有参考价值。第二，进行地址比较和计算时，务必先将指针转换为 uintptr_t 类型，不要直接比较 void*，因为在某些平台上，直接对 void* 进行算术或比较操作是未定义行为。