c - malloc() 是如何在内部实现的？

Question

谁能解释malloc()内部是如何工作的？

我有时做过strace program，我看到很多sbrk系统调用，man sbrk谈论它正在被使用，malloc()但不多。

Answer 1

sbrk系统调用移动数据段的“边界” 。这意味着它移动了程序可以读取/写入数据的区域的边界（让它增长或缩小，尽管 AFAIK 没有malloc真正使用该方法将内存段返回给内核）。除此之外，还有mmap用于将文件映射到内存但也用于分配内存（如果需要分配共享内存，mmap就是这样做的）。

所以你有两种从内核获取更多内存的方法：sbrk和mmap. 关于如何组织从内核获得的内存有多种策略。

一种天真的方法是将其划分为区域，通常称为“桶”，专用于某些结构大小。例如，一个malloc实现可以为 16、64、256 和 1024 字节结构创建存储桶。如果您要求malloc为您提供给定大小的内存，它将将该数字四舍五入到下一个桶大小，然后为您提供该桶中的一个元素。如果需要更大的区域malloc可以用mmap内核直接分配。如果某个大小的桶是空的malloc，可以用来sbrk为新桶获取更多空间。

有多种malloc设计，可能没有一种真正的实现方式，malloc因为您需要在速度、开销和避免碎片/空间效率之间做出折衷。例如，如果一个桶用完了元素，一个实现可能会从一个更大的桶中获取一个元素，将其拆分并将其添加到用完元素的桶中。这将非常节省空间，但并非每种设计都可能。如果您只是通过sbrk/获得另一个桶，mmap这可能会更快，甚至更容易，但空间效率不高。此外，设计当然必须考虑到“免费”需要以malloc某种方式再次提供可用空间。你不只是分发内存而不重用它。

如果您有兴趣，OpenSER/Kamailio SIP 代理有两种malloc实现（它们需要自己的实现，因为它们大量使用共享内存并且系统malloc不支持共享内存）。见：https ://github.com/OpenSIPS/opensips/tree/master/mem

然后你也可以看一下GNU libc mallocimplementation，但是那个很复杂，IIRC。

Answer 2

简单地说malloc，free像这样工作：

malloc提供对进程堆的访问。堆是 C 核心库（通常是libc）中的一个构造，它允许对象获得对进程堆上某些空间的独占访问权。

堆上的每个分配称为堆单元。这通常包括一个包含单元大小信息的标头以及指向下一个堆单元的指针。这使得堆有效地成为链表。

当一个进程启动时，堆包含一个单元，其中包含启动时分配的所有堆空间。该单元存在于堆的空闲列表中。

当调用malloc时，内存从大堆单元中取出，由malloc. 其余部分形成一个新的堆单元，由所有其余内存组成。

当一个人释放内存时，堆单元被添加到堆的空闲列表的末尾。随后malloc的走自由列表寻找合适大小的单元格。

正如可以预料的那样，堆可能会变得碎片化，并且堆管理器可能会不时尝试合并相邻的堆单元。

当空闲列表上没有用于所需分配的内存时，malloc调用brk或sbrk哪些系统调用从操作系统请求更多内存页面。

现在有一些修改来优化堆操作。

• 对于大内存分配（通常 > 512 字节，堆管理器可能会直接进入操作系统并分配完整的内存页面。
• 堆可以指定最小分配大小以防止大量碎片。
• 堆也可以将自己划分为一个用于小分配的箱，一个用于较大分配的箱，以便更快地进行较大的分配。
• 还有一些优化多线程堆分配的巧妙机制。

Answer 3

同样重要的是要意识到，只是简单地移动程序中断指针brk而不sbrk实际分配内存，它只是设置地址空间。例如，在 Linux 上，当访问该地址范围时，内存将由实际物理页面“支持”，这将导致页面错误，并最终导致内核调用页面分配器以获取支持页面。