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实现,但那个非常复杂,IIRC.

Answer 2

简单的malloc和免费工作如下:

malloc提供对进程堆的访问.堆是C核库(通常是libc)中的一个构造,它允许对象获得对进程堆上某些空间的独占访问.

堆上的每个分配称为堆单元.这通常由一个标题组成,该标题包含有关单元格大小的信息以及指向下一个堆单元格的指针.这使得堆有效地成为链表.

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

当一个人调用malloc时,内存是从大堆单元格中获取的,这是由malloc返回的.其余部分形成一个新的堆单元,由剩余的内存组成.

当释放内存时,堆单元格将添加到堆的空闲列表的末尾.随后的mallocs走自由列表寻找合适大小的单元格.

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

当空闲列表中没有剩余内存用于所需的分配时,malloc调用brk或sbrk,它们是从操作系统请求更多内存页的系统调用.

现在有一些优化堆操作的修改.

• 对于大内存分配(通常> 512字节,堆管理器可以直接进入操作系统并分配完整的内存页面.
• 堆可以指定最小分配大小以防止大量碎片.
• 堆也可以将其自身分成一个用于小分配的分区和一个用于较大分配的分区以更快地进行更大的分配.
• 还有用于优化多线程堆分配的聪明机制.

Answer 3

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