分析musl libc 1.2.0 malloc实现
musl libc
最近决定着手malloc的实现，一方面是比较感兴趣，另一方面可以加强对内存管理的理解，同时也可以推进对堆安全的理解。
相对于glibc的复杂，或许应该先抛开复杂的性能优化，从最简单的开始学习
所以我选择了musl libc 1.2.0版本
musl libc的malloc在1.2.1的版本进行了重构，重写了新的内存分配器，但是要复杂的多。
所以我选择了重构前的最新版本，也就是1.2.0进行学习
Source Code
将代码下载下来后，笔者使用 clangd + neovim 作为开发环境，所以先生成 compile_commands.json 数据库，便于使用跳转等高级功能
cd musl-1.2.0 && ./configure
bear -- make
数据结构
malloc的实现源码在 src/malloc 目录中，我们先来查看数据结构设计
struct chunk {
size_t psize, csize;
struct chunk *next, *prev;
};
struct bin {
volatile int lock[2];
struct chunk *head;
struct chunk *tail;
};
bin维护了一个带锁空闲双向链表，维护空闲chunk
In-band Metadata allocator
这个分配器的设计解决了好几个问题：
边界标记（Boundary Tags）
为了应对内存碎片化，每个chunk中都记录了前一个chunk大小（psize），和当前chunk大小（csize）
这样就可以在O(1)的复杂度中，快速找到上一个chunk和下一个chunk的起始地址
空间复用（Space Multiplexing）
一个chunk只有两个状态，一个是被分配，一个是未未分配
在空闲时，chunk就需要prev和next指针。 但是分配器在把内存交给用户时，直接把用户的起始写入地址指向了
next指针原本所在的位置。用户的数据直接覆盖并占用了原本存放指针的空间。动态切割
如果申请32字节，会从大块所在的 Bin 中拿出一个 1024 字节的 chunk，进行分割，切出 32 字节封装成新的 chunk 交给用户，剩下的 992 字节重新封装成一个更小的空闲 chunk，挂回到对应 992 字节大小的 Bin 里。
大小分级与隔离池
当堆里有成千上万个大小不一的空闲 chunk 时，当用户调用
malloc(32)，系统不能从头到尾遍历整个堆去寻找合适的内存引入
bin数组。系统按大小范围对空闲块进行分类，比如 Bin 1 专放 16-24 字节，Bin 2 专放 32-40 字节，以此类推。当申请特定大小的内存时，系统直接计算出对应的 Bin 索引，去该 Bin 的
head处摘取第一个空闲块。这也把查找时间降到了几乎 O(1)。
