C++内存分配器架构

Question

我需要在Linux下为C++编写Hoard分配器。虽然算法很简单，但我不知道在哪里（以及如何）存储分配器数据（例如堆）。

我的理解是：分配器不是进程，它是一组函数，任何应用程序都可以使用。每个应用程序都有自己的堆。

1. 应用程序启动时发生了什么？
2. 分配器如何找出已经创建了堆？
3. 分配器如何创建、存储和销毁（关闭应用程序时）堆？
4. 调用函数时，如何确定它在哪个线程（或处理器）上运行？

- i.y.

---

请查看https://dev59.com/NHA75IYBdhLWcg3wUHWQ，获取一些有用的信息。 - Carl Norum

我能找到的关于Hoard实际工作原理的唯一文档是源代码。个人而言，我建议你要么使用GPL版本的Hoard，要么让资助你的人支付商业版本的许可费用。 - Omnifarious

我认为你对用户空间分配器的作用有根本性的误解。否则很难理解你为什么会问第三个问题。 - David Schwartz

Answer 1

1. 除非分配器被设计并连接到应用程序启动代码中以预先请求一些内存，否则在应用程序启动期间可能不会发生太多事情。
2. 堆实际上并没有被创建。当需要内存时，分配系统会向操作系统请求一些内存 - 无论是为了其初始设置还是后来需要额外的内存来满足所请求的分配。在类Unix系统上，经常使用的系统调用称为 sbrk。（严格来说，在 Linux 上，sbrk 是对 brk 系统调用的库函数包装器 - 这可能或可能不是你关心的重要区别。）
3. 分配器使用上述提到的 sbrk 调用从操作系统获取内存。之后，它就自行管理该内存。当应用程序退出时，操作系统会回收内存 - 它知道通过 sbrk 调用分配的内存，因此它知道需要收回哪些内存。
4. 几乎从不重要的是给定代码片段运行在哪个线程或处理器上 - 如果您稍微解释一下您的问题背景，我会尽力回答。

- Carl Norum

---

这基本上是正确的，但并非完全正确。分配器也经常使用mmap /dev/zero来获取非常大的内存块。不过这只是一个边缘情况。 - Omnifarious

绝对正确。随着操作系统的不同，有着同样多的实现方式。过于亲密地与任何特定实现打交道通常意味着您正在用一种艰难的方式做某事。 - Carl Norum

这是一篇描述算法的论文。对于小对象（例如一个int），不使用mmap进行分配，而是为每个处理器分配堆，在其中分配这些对象。问题是：如何创建、存储和访问这些堆？你说过“之后就是独立管理该内存了”，这就是问题所在：分配器如何管理它的内存？它怎么知道哪些内存已经被分配给它了？ - i.y.

@i.y. - 请了解sbrk系统调用。内存分配器的工作是在适当的时候进行该系统调用，并维护描述使用sbrk调用获得的内存的哪些部分是空闲的，哪些是已分配的内部数据结构。 - Omnifarious

+1 @Omnifarious。在某种程度上，您可以把sbrk看作是malloc的malloc......如果这有任何意义的话。=) - Carl Norum

Answer 2

应用程序启动时发生了什么？

当应用程序启动时，分配器会初始化自身。如果您愿意，可以在第一次调用分配器时执行此操作。

分配器如何找出堆已经创建？

我不确定我是否理解了这个问题。如果您谈论的是由使用此分配器的代码管理的堆，则它会在创建堆时创建跟踪条目以找出。如果您谈论其他进程中的堆或由其他分配器创建的堆，则它不关心，因为它无法使用这些堆。

分配器如何创建、存储和销毁（关闭应用程序时）堆？

通常情况下，您有一个低级别和高级别的分配器。低级别分配器只从操作系统获取原始内存块。具体机制因平台而异。高级别分配器管理堆，并从低级别分配器获取保存堆结构的内存。

当调用函数时，如何找出它在哪个线程（或哪个处理器）上运行？

您可以通过线程特定数据或调用平台特定的“获取线程ID”函数来查找线程。至于哪个处理器，这非常依赖于平台，而且信息可能在您获得它时已经过时了。大多数平台确实有这样的功能 - 只需记住，您只能将其用作优化（以减少锁争用或提高缓存命中率）。关键是，您不能使用它来绕过锁定，因为线程随时可以从一个处理器移动到另一个处理器。

老实说，提供良好性能并可在各种平台上移植的内存分配确实是一种重度巫术。如果您不是该领域的专家，则很难开发出为生产应用程序提供所需性能和稳定性的分配器。

- David Schwartz

Answer 3

你在说什么“编写Hoard分配器”？有人已经编写了这个分配器。你是想从C++中使用它吗？Emery Berger的Hoard内部工作原理在白皮书《Hoard：一种可扩展的用于多线程应用程序的内存分配器》中有详细描述。所有那些无法解答的问题都可以通过阅读源代码或联系作者来解决。如果没有邮件列表，我会感到惊讶的。

- Kaz

---

这实际上是一项作业。算法很清晰，问题在于分配器的架构。 - i.y.