关于 malloc:C – 设计自己的 free() 函数

你不能盲目地设计 free() 而不知道 malloc() 是如何工作的，因为你的 free() 实现需要知道如何操作簿记数据，而在不知道如何操作的情况下这是不可能的malloc() 已实现。

所以一个不可回答的问题可能是你将如何设计 malloc() 和 free() 而不是一个微不足道的问题，但你可以部分回答它，例如通过提出一些非常简单的内存池实现，它不会等效当然到 malloc()，但会表明你有知识。

434511

malloc 和 free 仅在您的应用程序要在操作系统之上运行时才有意义。如果您想编写自己的内存管理函数，您必须知道如何从该特定操作系统请求内存，或者您可以使用现有的 malloc 立即保留堆内存，然后使用您自己的函数来分发/重新分配通过你的应用程序分配的内存

434511

内存使用模式可能是一个因素。 free 的默认实现不能假设您分配/解除分配的频率以及分配时分配的大小。

例如，如果您经常分配和释放大小相似的对象，则可以通过使用内存池来提高速度、内存效率并减少碎片。

编辑：正如 sharptooth 所指出的，只有将 free 和 malloc 一起设计才有意义。所以首先要弄清楚 malloc 是如何实现的。

434511

当您只能访问用户空间(通常称为内存池)时，一种常见的方法是在应用程序启动时从操作系统获取大量内存。您的 malloc 需要检查该池的正确大小的哪些区域仍然空闲(通过某些数据结构)并分发指向该内存的指针。您的 free 需要在数据结构中再次将内存标记为空闲，并且可能需要检查池的碎片。

好处是你可以在几乎恒定的时间内进行分配，缺点是你的应用程序消耗的内存比实际需要的多。

434511

malloc 和 free 应该遵循一种架构——本质上是一种允许不同策略共存的类架构。那么执行的free版本对应使用的malloc版本。

但是，我不确定这种架构的观察频率。

434511

这实际上是一个非常模糊的问题，这可能就是您感到困惑的原因。他的意思是，给定现有的 malloc 实现，您将如何尝试开发一种更有效的方法来释放底层内存？还是他希望您开始讨论不同类型的 malloc 实现以及它们的好处和问题？他是否希望您知道虚拟内存在 x86 架构上的功能？

另外，更高效是指更节省空间还是更节省时间？ free() 必须是确定性的吗？它是否必须尽可能多地将内存返回给操作系统，因为它处于低内存、多任务环境中？我们这里的标准是什么？

除了开始问自己的问题以获得澄清之外，很难说从哪里开始像这样模糊的问题。毕竟要设计自己的free函数，首先要知道malloc是如何实现的。所以很有可能，问题实际上是关于您是否知道如何实现 malloc。

如果您不熟悉内存管理的内部原理，了解 malloc 是如何实现的最简单的方法是首先编写自己的。

对于初学者来说，查看这篇名为”内部内存管理”的 IBM DeveloperWorks 文章。

但在您编写自己的 malloc/free 之前，您首先需要分配/释放内存。不幸的是，在受保护模式的操作系统中，您不能直接寻址机器上的内存。那么怎么获得呢？

你向操作系统索要它。借助 x86 的虚拟内存特性，任何一块 RAM 或交换内存都可以由操作系统映射到内存地址。您的程序所看到的内存可能在整个系统中物理上是碎片化的，但是由于内核的虚拟内存管理器，它看起来都一样。

内核通常提供系统调用，允许您为进程映射额外的内存。在较旧的 UNIX 操作系统上，这通常是 brk/sbrk 将堆内存增长到进程的边缘或将其缩小，但是许多系统还提供 mmap/munmap 来简单地映射一大块堆内存。它仅当您可以访问需要 malloc/free 来管理它的大型、连续的内存块时。

一旦你的进程有一些可用的堆内存，它就是把它分成块，每个块包含它自己的元信息，关于它的大小和位置以及它是否被分配，然后管理这些块。一个简单的结构列表，每个都包含一些元信息字段和一个大字节数组，可以工作，在这种情况下 malloc 必须遍历列表，直到找到足够大的未分配块(或它可以组合的块)，并且如果找不到足够大的块，则映射更多内存。一旦你找到一个块，你只需返回一个指向数据的指针。 free() 然后可以使用该指针将几个字节反转回结构中存在的成员字段，然后可以对其进行修改(即标记 chunk.allocated = false;)。如果列表末尾有足够多的未分配块，您甚至可以将它们从列表中删除，然后从进程堆中取消映射或缩小该内存。

不过，这是一个真正简单的实现 malloc 的方法。你可以想象，有很多可能的方法可以将你的内存分成块然后管理这些块。有多少数据结构和算法就有多少方法。它们也都是为不同的目的而设计的，比如限制由于小的、已分配的块与小的、未分配的块混合而导致的碎片，或者确保 malloc 和 free 运行得快(或者有时甚至更慢，但可以预见地慢)。有 dlmalloc、ptmalloc、jemalloc、Hoard 的 malloc 等等，其中许多都非常小而简洁，所以不要害怕阅读它们。如果我没记错的话，Kernighan 和 Ritchie 的”The C Programming Language”甚至使用了一个简单的 malloc 实现作为他们的示例之一。

434511

malloc()的工作知识是实现free()所必需的。您可以使用 K 中的 sbrk() 系统调用找到 malloc() 和 free() 的实现

你不能盲目地设计 free() 而不知道 malloc() 是如何工作的，因为你的 free() 实现需要知道如何操作簿记数据，而在不知道如何操作的情况下这是不可能的malloc() 已实现。

所以一个不可回答的问题可能是你将如何设计 malloc() 和 free() 而不是一个微不足道的问题，但你可以部分回答它，例如通过提出一些非常简单的内存池实现，它不会等效当然到 malloc()，但会表明你有知识。

434511

malloc 和 free 仅在您的应用程序要在操作系统之上运行时才有意义。如果您想编写自己的内存管理函数，您必须知道如何从该特定操作系统请求内存，或者您可以使用现有的 malloc 立即保留堆内存，然后使用您自己的函数来分发/重新分配通过你的应用程序分配的内存

434511

内存使用模式可能是一个因素。 free 的默认实现不能假设您分配/解除分配的频率以及分配时分配的大小。

例如，如果您经常分配和释放大小相似的对象，则可以通过使用内存池来提高速度、内存效率并减少碎片。

编辑：正如 sharptooth 所指出的，只有将 free 和 malloc 一起设计才有意义。所以首先要弄清楚 malloc 是如何实现的。

434511

当您只能访问用户空间(通常称为内存池)时，一种常见的方法是在应用程序启动时从操作系统获取大量内存。您的 malloc 需要检查该池的正确大小的哪些区域仍然空闲(通过某些数据结构)并分发指向该内存的指针。您的 free 需要在数据结构中再次将内存标记为空闲，并且可能需要检查池的碎片。

好处是你可以在几乎恒定的时间内进行分配，缺点是你的应用程序消耗的内存比实际需要的多。

434511

malloc 和 free 应该遵循一种架构——本质上是一种允许不同策略共存的类架构。那么执行的free版本对应使用的malloc版本。

但是，我不确定这种架构的观察频率。

434511

这实际上是一个非常模糊的问题，这可能就是您感到困惑的原因。他的意思是，给定现有的 malloc 实现，您将如何尝试开发一种更有效的方法来释放底层内存？还是他希望您开始讨论不同类型的 malloc 实现以及它们的好处和问题？他是否希望您知道虚拟内存在 x86 架构上的功能？

另外，更高效是指更节省空间还是更节省时间？ free() 必须是确定性的吗？它是否必须尽可能多地将内存返回给操作系统，因为它处于低内存、多任务环境中？我们这里的标准是什么？

除了开始问自己的问题以获得澄清之外，很难说从哪里开始像这样模糊的问题。毕竟要设计自己的free函数，首先要知道malloc是如何实现的。所以很有可能，问题实际上是关于您是否知道如何实现 malloc。

如果您不熟悉内存管理的内部原理，了解 malloc 是如何实现的最简单的方法是首先编写自己的。

对于初学者来说，查看这篇名为”内部内存管理”的 IBM DeveloperWorks 文章。

但在您编写自己的 malloc/free 之前，您首先需要分配/释放内存。不幸的是，在受保护模式的操作系统中，您不能直接寻址机器上的内存。那么怎么获得呢？

你向操作系统索要它。借助 x86 的虚拟内存特性，任何一块 RAM 或交换内存都可以由操作系统映射到内存地址。您的程序所看到的内存可能在整个系统中物理上是碎片化的，但是由于内核的虚拟内存管理器，它看起来都一样。

内核通常提供系统调用，允许您为进程映射额外的内存。在较旧的 UNIX 操作系统上，这通常是 brk/sbrk 将堆内存增长到进程的边缘或将其缩小，但是许多系统还提供 mmap/munmap 来简单地映射一大块堆内存。它仅当您可以访问需要 malloc/free 来管理它的大型、连续的内存块时。

一旦你的进程有一些可用的堆内存，它就是把它分成块，每个块包含它自己的元信息，关于它的大小和位置以及它是否被分配，然后管理这些块。一个简单的结构列表，每个都包含一些元信息字段和一个大字节数组，可以工作，在这种情况下 malloc 必须遍历列表，直到找到足够大的未分配块(或它可以组合的块)，并且如果找不到足够大的块，则映射更多内存。一旦你找到一个块，你只需返回一个指向数据的指针。 free() 然后可以使用该指针将几个字节反转回结构中存在的成员字段，然后可以对其进行修改(即标记 chunk.allocated = false;)。如果列表末尾有足够多的未分配块，您甚至可以将它们从列表中删除，然后从进程堆中取消映射或缩小该内存。

不过，这是一个真正简单的实现 malloc 的方法。你可以想象，有很多可能的方法可以将你的内存分成块然后管理这些块。有多少数据结构和算法就有多少方法。它们也都是为不同的目的而设计的，比如限制由于小的、已分配的块与小的、未分配的块混合而导致的碎片，或者确保 malloc 和 free 运行得快(或者有时甚至更慢，但可以预见地慢)。有 dlmalloc、ptmalloc、jemalloc、Hoard 的 malloc 等等，其中许多都非常小而简洁，所以不要害怕阅读它们。如果我没记错的话，Kernighan 和 Ritchie 的”The C Programming Language”甚至使用了一个简单的 malloc 实现作为他们的示例之一。

434511

malloc()的工作知识是实现free()所必需的。您可以使用 K 中的 sbrk() 系统调用找到 malloc() 和 free() 的实现