一、内存布局
图 1：内存布局示意图（栈向下扩展，堆向上扩展）
由上图可知，栈至顶向下扩展，堆至底向上扩展。
二、brk（sbrk）和 mmap 函数
1. brk（sbrk）
在 Linux 系统中，malloc 底层主要通过 brk、sbrk 和 mmap 这几个系统调用来实现内存的分配和管理。
#include <unistd.h>
void *brk(const void *addr);
void *sbrk(intptr_t incr);
两者的作用是扩展 heap 的上界 brk。
brk()：参数设置为新的 brk 上界地址，成功返回 0，失败返回 -1；如果 addr 大于当前的程序中断点，就会扩大数据段，分配新的内存；如果 addr 小于当前的程序中断点，就会缩小数据段，释放内存。sbrk()：参数为申请内存的大小，返回 heap 新的上界 brk 的地址；当 increment 为正数时，堆顶指针会向高地址移动，分配内存；当 increment 为负数时，堆顶指针会向低地址移动，释放内存。
2. mmap
#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);
mmap() 进行内存分配（malloc）时一般使用后者，前者主要是进行文件映射。
mmap 分配内存比较直接，相对的开销也较大，释放也比较简单，通过 munmap 函数可以立即将内存归还给操作系统。
一般来说，当 malloc 申请的内存较小时，会使用 brk 或 sbrk 来扩展堆内存；而当申请的内存较大时（通常阈值为 128KB），会直接使用 mmap 在内存映射区申请内存。
但是，如果每次申请内存都调用这些接口的话，势必会影响系统的性能，并且也极容易产生内存碎片。所以 malloc 采用 ptmalloc（内存池管理机制）对内存的分配与回收进行管理。
3. ptmalloc
ptmalloc 会预先向操作系统申请一块内存供用户使用，当我们申请和释放内存的时候，ptmalloc 会将这些内存管理起来，并通过一些策略来判断是否将其回收给操作系统。
3.1 chunk(内存块基本结构)
在 ptmalloc 中，内存是由一个个 chunk 组成，每个 chunk 由结构体 malloc_chunk 进行描述：
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; // 前一个 chunk 的大小（如果前一个 chunk 是空闲的）
INTERNAL_SIZE_T size; // 当前 chunk 的大小，包括头部开销
struct malloc_chunk *fd; // 双向链表指针，指向下一个空闲 chunk（仅当 chunk 空闲时使用）
struct malloc_chunk *bk; // 双向链表指针，指向上一个空闲 chunk（仅当 chunk 空闲时使用）
/* 当前的 chunk 存在于 large bins 中时使用 */
struct malloc_chunk *fd_nextsize;
/* 仅当 chunk 空闲时使用 */
struct malloc_chunk *bk_nextsize;
};
prev_size：表示前一个空闲的 chunk 大小，如果前一个 chunk 不空闲，该字段无意义，prev_size主要用于相邻空闲 chunk 的合并。size：当前 chunk 的大小和一些其他信息，其中低三位（A,M,P）中记录包括前一个 chunk 是否在使用中，当前 chunk 是否是通过 mmap 获得的内存，当前 chunk 是否属于非主分配区。fd和bk：这两兄弟只有当该 chunk 块空闲时才存在，其作用是用于将对应的空闲 chunk 块加入到空闲 chunk 块链表中进行管理。例如，当一个 chunk 被释放时，它会根据 size 字段中的信息找到前一个和后一个 chunk，判断它们是否空闲，如果空闲则进行合并，然后将合并后的 chunk 通过这两个指针插入到相应的空闲链表中。如果该 chunk 块被分配给了应用程序使用，那么这两个指针被当作应用程序的使用空间，不会浪费。fd_nextsize和bk_nextsize：和 fd、bk 类似。
注意：当 chunk 为空时才有 fd、bk、fd_nextsize、bk_nextsize 四个指针，当 chunk 不为空，这四个指针的空间是直接交给用户使用的。
3.2 malloc 分配大体流程
- 搜索空闲链表：首先，ptmalloc 会在快速链表（fast bins）（小于 4 字节）、小链表（small bins）和大链表（large bins）中查找是否有合适大小的空闲 chunk。快速链表用于管理小且常用大小的 chunk，这些 chunk 在释放时不会与相邻的 chunk 合并，分配速度很快；小链表中的 chunk 大小固定且不超过 512 字节，按大小顺序排列；大链表中的 chunk 大小大于 512 字节。如果在这些链表中找到了合适的 chunk，就直接返回该 chunk 给用户。
- 扩展堆或使用 mmap：如果在空闲链表中没有找到合适的 chunk，ptmalloc 会尝试从堆顶的 top chunk 中分配内存。（top chunk 相当于分配区的顶部空闲内存）如果 top chunk 的大小足够，就从 top chunk 中分割出一块满足需求的内存返回给用户，剩余部分成为新的 top chunk；如果 top chunk 的大小不足，且申请的内存小于一定阈值（如 128KB），ptmalloc 会调用 sbrk 扩展堆内存，然后从新扩展的内存中分配；如果申请的内存大于阈值，ptmalloc 会使用 mmap 将内存放到 mmaped chunk 上，当释放 mmaped chunk 上的内存的时候会直接交还给操作系统。
- 大块拆分：当从大链表中找到一个大于请求大小的 chunk 时，ptmalloc 会将该 chunk 拆分成两部分，一部分满足请求大小返回给用户，另一部分作为剩余块（remainder chunk），根据其大小插入到合适的空闲链表中。
3.3 释放流程
当调用 free 释放内存时，ptmalloc 会执行以下操作：
- 标记为空闲：首先将释放的 chunk 标记为空闲状态，并根据 chunk 的大小和标志位判断是否需要与相邻的空闲 chunk 进行合并。
- 合并相邻空闲块：如果当前 chunk 的前一个和后一个 chunk 都是空闲的，ptmalloc 会将它们合并成一个大的 chunk，减少内存碎片。合并后的 chunk 会被插入到合适的空闲链表中。
- 缩小堆：如果释放的 chunk 与 top chunk 相邻，且合并后的 top chunk 足够大（超过一定阈值），ptmalloc 会调用 sbrk 缩小堆内存，将多余的内存归还给操作系统。
