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 malloc implementation，但这是一个非常复杂，IIRC。

Answer 2

简单地malloc和free的工作是这样的：

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

堆上的每个分配称为堆单元。这通常由一个头部组成，该头部保存关于单元大小的信息以及指向下一个堆单元的指针。这使得一个堆有效地成为一个链表。

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

当一个调用malloc，存储器从大堆单元，其通过malloc返回截取。其余部分形成一个由所有其余内存组成的新堆单元。

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

可以预料，堆可能会碎片化，堆管理器可能会不时尝试合并相邻的堆单元。

当没有留下所需的分配空闲列表上的内存，malloc的调用BRK或SBRK这是系统调用请求从操作系统中多个存储页。

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

• 对于大的存储器分配 （典型地> 512个字节，堆 管理器可以直接进入OS和 分配一个完整的存储器页面。
• 堆 可以指定 分配的最小尺寸，以防止大量碎片 。
• 堆也可能本身分为频段的一个为小分配和一个较大的分配做出了较大的分配速度更快。
• 还有人如此巧妙的机制来优化多线程堆分配。

Answer 3

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