使用 sbrk 和 mmap 这两个系统调用可以向操作系统申请堆内存，但这种分配内存的方式效率比较低，因为执行系统调用是要进入内核态的，运行态的切换会耗费不少时间。为了解决这个问题，比较倾向于使用系统调用来分配大块内存，然后再把这块内存分割成更小的块，以方便程序员使用，这样可以提升分配的效率。
C 语言的运行时库 glibc 主要提供 malloc 和 free 等库函数给程序员。malloc 实现的基本原理是先向操作系统申请一块比较大的内存，然后再通过各种优化手段让内存分配的效率最大化。

malloc 的实现原理

内存的精细化管理，主要考虑两个因素，一是分配和回收的效率，二是内存区域的有效利用率（内存的块内碎片以及块间碎片）

空闲链表

对小块内存进行精细化管理，最常用的数据结构就是链表。为了能够方便地进行分配和回收，把空闲区域记录到链表里，这就是空闲链表 (free list)。空闲链表里的节点主要是为了记录内存的开始位置和长度。

上图中展示了一个总长度为 100 的内存区域，已经分割成 16、16、20、16、16、16 六个小的内存块。其中着色部分，也就是第一、第三和第五块内存是已经分配出去的，正在使用的内存，而白色区域则是尚未分配的内存。图的上半部分代表空闲链表，每一块未分配的内存都会由一个空闲链表的节点进行管理。

当分配内存的请求到达以后，就通过遍历 free list 来查找可用的空闲内存区域，在找到合适的空闲区域以后，就将这一块区域从链表中摘下来。比如要请求的大小是 m，就将这个结点从链表中取下，把起始位置向后移动 m，大小也相应的减小 m，并将修改后的结点重新挂到链表上。
在释放的时候，将这块区域按照起始起址的排序放回到链表里，并且检查它的前后是否有空闲区域，如果有就合并成一个更大的空闲区。
对于这种简单算法（此策略被称为 First Fit，此外还有 Best Fit 以及 Next Fit 等策略，但这些碎片都难以解决内存碎片问题），比较容易产生内存碎片（比如上图尽管空闲内存总和有 48 字节，却难以分配大于 20 字节的连续内存）。由于每一次分配内存时，都需要遍历 free list，因此最差情况下的时间复杂度是 O(n)，分配效率也较低。此外，对于多线程下并发的内存分配请求，free list 会成为临界区，为保护临界资源需要采用相应的同步机制，这样会导致性能进一步恶化。

分桶式内存管理

分桶式内存管理采用了多个链表，对于单个链表，它内部的所有结点所对应的内存区域的大小是相同的。换句话说，相同大小的区域会挂载到同一个链表上。最常见的方式是以 4 字节为最小单位，把所有 4 字节的区域挂到同一个链表上，再把 8 字节的区域挂到一起，然后是 16 字节，32 字节，这样以 2 次幂向上增长。如下图所示：

采用了新的数据结构以后，分配和回收的算法也相应地发生了变化。首先，分配的时候，只需找到能满足这一次分配请求的最小区域，然后去相应的链表里把整块区域都取下来。比如，分配一个 7 字节的内存块时，就可以从 8 字节大小的空闲链表里直接取出链表头上的那块区域，分配给应用程序。由于从链表头上删除元素的时间复杂度是 O(1)，所以分配内存的效率就大大提高了。由于整个大块内存被提前分割成了整齐的小块（比如是以 4 字节对齐），所以整个区域里不存在块与块之间内存碎片，但仍可能存在内部碎片。释放时，只需要把要释放的内存直接插入到相应的链表的头部就可以了，时间复杂度也是 O(1)。
分桶式内存管理比简单算法无论是在算法效率方面，还是在碎片控制方面都有很大的提升。但它的缺陷也很明显：区域内部的使用率不够高和动态扩展能力不够好。例如，4 字节的区域提前消耗完了，但 8 字节的空闲区域还有很多，此时就会面临两难选择，如果直接分配 8 字节的区域，则区域内部浪费就比较多，如果不分配，则明明还有空闲区域，却无法成功分配。
为了解决上述两个问题，人们在分桶的基础上提出伙伴系统，让内存可以根据需求动态地决定小的内存区域和大的内存区域的比例。

伙伴系统

对于上面的分桶式内存管理，当系统中还有很多 8 字节的空闲块，而 4 字节的空闲块却已经耗尽，这时再有一个 4 字节的请求，则会出现 malloc 失败的情况。为了避免分配失败，可以考虑将大块的内存做一次拆分。

如上图所示，分配一块 4 字节大小的空间，在 4 字节的 free list 上找不到空闲区域，系统就会往上找，假如 8 字节和 16 字节的 free list 中也没有空闲区域，就会一直向上找到 32 字节的 free list。伙伴系统不会直接把 32 的空闲区域分配出去，因为这样做的话，会带来巨大的浪费。它会先把 32 字节分成两个 16 字节，把后边一个挂入到 16 字节的 free list 中。然后继续拆分前一半。前一半继续拆成两个 8 字节，再把后一半挂入到 8 字节的 free list，最后，把前一半 8 字节拿去分配，当然这里也要继续拆分成两个 4 字节的空闲区域，其中一个用于本次 malloc 分配，另一个则挂入到 4 字节的 free list。分配后的内存的状态如下图所示：

这种不断地把一块内存分割成更小的两块内存的做法，就是伙伴系统，这两块更小的内存就是伙伴。 它的好处是可以动态地根据分配请求将大的内存分割成小的内存。当释放内存时，如果系统发现与被释放的内存相邻的那个伙伴也是空闲的，就会把它们合并成一个更大的连续内存。通过这种拆分，系统就变得更加富有弹性。
malloc 的实现，在历史上先后共有几十种策略，这些策略往往就是上述三种算法的组合。具体到 glibc 中的 malloc 实现，它就采用了分桶的策略，但是它的每个桶里的内存不是固定大小的，而是采用了将 1 ~ 4 字节的块挂到第一个链表里，将 5 ~ 8 字节的块挂到第二个链表里，将 9~16 字节的块挂到第三个链表里，依次类推。在单个链表内部则采用 naive 的分配方式，比如要分配 5 个字节的内存块，会先在 5 ~ 8 这个链表里查找，如果查找到的内存大小是 8 字节的，那就会将这个区域分割成 5 字节和 3 字节两个部分，其中 5 字节用于分配，剩余的 3 字节的空闲区域则会挂载到 1~4 这个链表里。
malloc 的实现策略是比较灵活的，针对不同的场景，不同的分配策略的性能表现也是不一样的。很多公司的基础平台都选择自己实现内存池来提供 malloc 接口，这样可以更好地服务本公司的业务。
最著名的例子就是 Google 公司实现的 Tcmalloc 库，相比起其他的 malloc 实现，最大的改进是在多线程的情况下性能提升。在多线程并发地分配内存时，每次分配都要对 free list 进行加锁以避免并发程序带来的问题，这就容易形成性能瓶颈。为了解决这个问题，Tcmalloc 引入了线程本地缓存 (Thread Local Cache)，每个线程在分配内存的时候都先在自己的本地缓存中寻找，如果找到就结束，只有找不到的情况才会继续向全局管理器申请一块大的空闲区域，然后按照伙伴系统的方式继续添加到本地缓存中去。

malloc 和 mmap 的区别和联系

malloc 和 mmap 的区别，从实现机制上来说，mmap 是操作系统提供的系统调用，而 malloc 是 glibc 提供的分配内存的接口，而从作用上来说，malloc 主要是用于分配堆内存，而 mmap 除了可以用于分配内存，还可以用于加载动态链接库，进行驱动文件映射以及加速 I/O，还可以创建共享内存用于进程间通信。而它们的联系在于，malloc 在向操作系统申请大块内存时需要依赖 mmap。

课外扩展

GDB 如何打印函数调用栈

valgrind 如何追踪内存泄漏