编写新的“malloc”和“free”函数

Question

关于面试问题：我如何编写新的“malloc”和“free”函数？我不认为“使用new和delete”或类似的LocalAlloc/HeapAlloc等功能是可接受的答案。

- Johnny Pauling

---

内存管理通常由操作系统负责处理，因此如果需要新的内存管理器或仅需要使用某些现有API的函数，则至少应该更加清晰明确。 - KBart

这个有用吗？http://login2win.blogspot.in/2011/06/c-heaps.html - NeonGlow

我认为这篇关于SO的帖子可能会回答你的问题，malloc是如何实现的？ - Raj

我会仔细查看我这样做的原因。现有的分配器有什么问题？我的要求是什么？ - David Schwartz

@ShaneMacLaughlin：没错。您可能需要在不同平台上实现可预测的行为。在多线程情况下，您可能需要更好的并发性。您可能需要更好地跟踪内存分配的位置。您可能需要分配一堆内存并将其作为一组释放。您可能需要更有效地将空闲内存返回给操作系统。您可能需要更好地运行时统计内存使用情况。如果不知道为什么就问如何做，那是疯狂的。（也许，这就是他们正在寻找的答案。） - David Schwartz

Answer 1

由于这是一个面试问题，可能没有“正确”答案，他们更关心的是您的思维过程和您对该主题的一般知识。

您应该要求澄清要求，或根据情况给出一系列答案。以下是需要考虑的一些问题：

• 避免内存碎片化是否重要？固定分配大小可能会有所帮助。
• 是否需要分配速度保证？使用已用/空闲块的索引。
• 您是否需要轻松跟踪执行的分配？向malloc/free库添加日志记录结构。
• 您是否需要防止或检测内存欠/溢出？额外的填充和定期的填充检查。

- congusbongus

---

他们寻找的不仅是答案，更关注你对问题的表述方式以及是否展现了对该领域的知识。 - David Schwartz

Answer 2

简单地说，你的malloc函数应该能够从操作系统获得内存，并将其提供给请求动态分配内存的客户端（比如，你的C程序）。为了实现这一点，malloc库通常需要许多数据结构（根据具体实现而定）——例如，malloc的实现可能选择使用链表跟踪空闲的内存块。更有效的方法是有一个链表列表，每个列表包含一定大小范围的块。

我碰巧在TCMalloc库上工作过，这可能会帮助您更清楚地了解这一点。

通过空闲链表进行内存分配

假设类0是大小为4k的空闲块的链接列表，类1是大小为8k的空闲块的链接列表，以此类推。

当调用malloc（比如，大小为10k）时，你的malloc实现会遍历freelist以找到最小的空闲块，该块可以满足请求（在这种情况下，4k块不足以满足请求，所以它会获取一个8k块，从freelist中删除它，并将其返回给你的程序）。

同样地，当调用free时，你的实现（除其他事项外）应该从程序中回收该块，并将其添加到适当的freelists中。

- Raj

Answer 3

这个网站回答了你的问题。

同样的问题可以在这里找到答案：http://www.codeproject.com/Questions/177316/Write-your-own-malloc 你也可以参考这个链接：http://www.inf.udec.cl/~leo/Malloc_tutorial.pdf

- napat

Answer 4

如果面试官问你如何编写新的“malloc”和“free”函数，而你开始谈论你将要做什么，那么你已经失败了。在此之前，您需要提出一些问题，以更精确地使用malloc功能。我头脑中首先想到的一些问题是：

• 针对哪个操作系统？
• 用于哪种内存？用户malloc还是内核malloc？
• 最常见的使用场景是哪一个？全用途malloc?更适合大块或小块?

在开始讨论代码之前，需要进行第一轮需求收集。

- UmNyobe

---

“你已经失败了” - 这是一个相当悲观的看法。 - Neowizard

@Neowizard 相信我，你需要这样做。至少会有一个候选人会遵循 Cong 和我的建议。在面试中，这个候选人已经领先于你了。 - UmNyobe

我从来没有参加过面试，面试官问我“诡计”问题。仅提供部分相关问题信息并不是测试候选人能力或思维方式的有效方式（在我看来）...但这只是我的看法。 - Neowizard

这段与编程有关的内容需要翻译成中文。请只返回已翻译的文本，不要进行解释。如果有人告诉你“为我建造一座桥”，而你甚至不知道这座桥将建在哪里，你的工作就会毫无意义。 - UmNyobe

如果有人在面试中让你建造一座桥，那将是一个非常漫长的面试。如果有人在工作中要求我写点什么，这与在面试中要求我“写”东西完全不同。一个不理解这种区别的面试官是另一个问题。 - Neowizard

Answer 5

如果你想要钩住 malloc() 和 free() 函数调用，可以使用类似以下的方式：

#define malloc(x) your_malloc(x)
#define free(x) your_free(x)

但是，如果你想创建自己的内存分配器，那么你可能需要查看 Kernighan 和 Ritchie 在他们的书 "C程序设计语言 第二版" 中实现的堆分配器之一。它基本上依赖于使用 sbrk() 系统函数来增加进程的数据段的大小。

- Aniket Inge

Answer 6

这取决于需求，例如，如果您想创建嵌入式软件，在运行时有时不允许使用malloc/free或因性能原因。那么您可以创建自己的版本的malloc/free，它不会分配/释放内存，而是从预先分配的堆中获取/返回块。

- AndersK

Answer 7

我想他们可以/应该用另一种方式来表达问题：“malloc和free如何管理堆内存？”

然后，您可以稍微以不同的方式考虑问题-给定一系列值的线性列表，如何划分出列表的块并跟踪它们，如何返回该列表的块，如何管理列表的碎片等。

简而言之，下一个空闲块的地址存储在已分配块旁边的堆中，存储下一个空闲内存块的信息对用户不可见，但仍属于同一堆。这就是为什么超出malloc内存范围可能会完全破坏堆并导致malloc和free等函数崩溃的原因。

---

通常面试官会利用问题给你自由发挥展示你的知识。你可以从基本功能开始，然后如果你很懂，可以继续讲述不同操作系统如何管理它，有哪些不同的算法等等。毕竟，无论你描述什么，都不可能涵盖过去二十年在这个领域的研究和开发！

- Joe