algorithm - 内存分配器的 "killer adversary"？

Question

看完this question关于 Windows 内存分配器看似退化的行为，并回想起 this paper关于构建快速排序实现的最坏情况输入，我开始想:是否有可能构建一个程序，给定一个黑盒内存分配器，强制该分配器使分配请求失败，即使系统中仍有足够的内存可用？也就是说，是否可以采用黑盒内存分配器并强制其失败？

我知道这可能可以通过以棋盘模式分配和释放内存来强制大量碎片来完成，所以在我看来，理想的解决方案会导致失败，并且在失败时分配的总字节数最少。关于激发此灵感的原始帖子，如果内存分配器存在内部错误，理论上可能会导致分配零字节的失败。

关于如何做到这一点的任何想法/想法？

Answer 1

取决于您所说的“足够的可用内存”是什么意思。对于简单的碎片“攻击”:

• 做一个 squillion small分配直到一个失败[*]。

• 现在，按照地址 [**] 的顺序对它们进行排序。

• 免费 100 次备用分配。

• 尝试分配 100*small字节。

很可能分配器无法找到连续的内存来满足它。如果它有 small页面大小，以及与物理内存相比大量的虚拟地址空间，那么它可能能够重新安排事情来做到这一点 - 但这需要 MMU 的能力在分配器的任何反碎片策略之上。

如果“足够的可用内存”是指 large以前是连续 block 的内存块，已被分成几个分配，所有这些分配都已被释放，现在分配器将其视为单独的 block ，因此无法分配 large bytes 那么不，我不认为你可以强制任意 block 盒分配器无法合并 block 。某些分配器或其他分配器可能比 Windows 在其他问题中所做的工作要多得多，以确保始终合并相邻的空闲 block 。

[*] 可能的问题 - 过度提交内存分配器可能不会失败，您只会遇到段错误或您的进程被终止。在此类系统上，您可能需要跟踪有多少内存可用。

[**] 可能的问题 - 在 C 和 C++ 中，operator<不能保证工作。但是在几乎所有的系统上它都会，在 C++ 中有 std::less也是。