前言

学习自《glibc内存管理ptmalloc源代码分析》庄明强 著
部分资料参考自互联网

chunk

描述：

1. 当用户通过malloc等函数申请空间时，实际上是从堆中分配内存
2. 目前 Linux 标准发行版中使用的是 glibc 中的堆分配器：ptmalloc2
3. ptmalloc根据用户的需要，为用户分配不同类型的chunk

结构体：

struct malloc_chunk {
    INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
    INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
    
    struct malloc_chunk* fd; /* double links -- used only if free. */
    struct malloc_chunk* bk;
    
    /* Only used for large blocks: pointer to next larger size. */
    struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
    struct malloc_chunk* bk_nextsize;
};

使用中（分配后）

chunk start：chunk的起始地址
previous size：

1. 上一个chunk的大小，32位占4字节，64位占8字节
2. 只有当上一个chunk处于空闲状态时才有效

size：

1. 当前chunk的大小，32位占4字节，64位占8字节
2. 后三个比特位为A|M|P标志位，分别代表不同含义
   A：为0表示该chunk属于主分配区，为1表示该chunk属于非主分配区
   M：表示当前chunk是从哪个内存区域获得的虚拟内存。为1表示该chunk是从mmap映射区域分配的，否则是从heap区域分配的
   P：为1表示前一个chunk正在使用中，当前chunk的prev_size无效，不能对前一个chunk进行任何操作。第一块heap总是将P设为1，以防止程序引用到不存在的区域

memory：malloc等函数返回给用户的chunk数据区指针

空闲中（释放后）

描述：

1. 空闲中的chunk不存在M状态，只有A|P状态
2. user data头部被分配出两个成员，fd和bk
   

fd：指向前一个空闲chunk的起始地址，32位占4字节，64位占8字节
bk：指向后一个空闲chunk的起始地址，32位占4字节，64位占8字节

注意：事实上，释放后的large block中还存在另外两个成员：fd_nextsize和bk_nextsize，后续再作介绍

堆块大小

32位程序：

1. 用户分配到的最小堆块大小为17B：prev_size(4B) + size(4B) + fd(4B) + bk(4B) + next_chunk->p(1B)
2. 若用户申请的大小超过最小堆块大小，会与8B进行对齐

64位程序：

1. 用户分配到的最小堆块大小为33B：prev_size(8B) + size(8B) + fd(8B) + bk(8B) + next_chunk->p(1B)
2. 若用户申请的大小超过最小堆块大小，会与16B进行对齐

空间复用

描述：当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 无效。所以下一个 chunk 的 prev_size 也可以被当前 chunk 使用，这就是 chunk 的空间复用

bins

描述：

1. 用户free掉的内存并不是都会马上归还给系统，ptmalloc会统一管理heap和mmap映射区域中的空闲的chunk
2. 当用户进行下一次分配请求时，ptmalloc会首先试图在空闲的chunk中挑选一块给用户，这样就避免了频繁的系统调用，降低了内存分配的开销
3. ptmalloc将相似大小的chunk用双向链表链接起来，这样的一个链表被称为一个bin
4. ptmalloc一共维护了128个bin，并使用一个数组来存储这些bin
5. 堆管理器根据特点，将堆分为四种：fastbin | unsortedbin | smallbin | largebin
6. 数组中bin 1为unsorted bin；bin 2到63为small bin；bin 64到126为large bin

fastbin

描述：

1. 在32位操作系统中，当用户释放的堆块大小小于64B时使用fastbin进行管理，即chunk空间最大为80字节
2. fastbin只使用了fd成员，是个单链表结构
3. fastbin不会对P位进行操作，也就是说它不会主动进行合并；只有在某些特定情况下，堆管理器才会对fastbin进行合并
4. fastbinY为管理fastbin的数组，每个成员分别管理不同大小的fastbin链表，且均指向了当前链表的尾节点，当尾节点被分配时，通过其fd指针指向前一个结点
5. 当用户申请chunk大小小于或等于MAX_FAST_SIZE时，优先从fastbins中查找相应的空闲块，且规则为LIFO（Last in, first out, 后进先出）
   

unsorted bin

描述：

1. 当释放较小或较大的chunk的时候，为了增加分配效率，系统会先将最近释放的chunk添加到unsorted bin中
2. unsorted bin 为一个双向循环链表，对chunk的大小没有限制，即任何大小的chunk都可以放入unsorted bin链表中

small bin

描述：

1. 在32位操作系统中，当用户释放的堆块大小大于64B，小于等于512B时使用small bin进行管理
2. small bin 为双向循环链表，且使用 FIFO（First in, first out, 先入先出） 算法
3. 当满足small bin条件的chunk被释放后，会优先被放入unosrted bin，只有在一定情况下，才会被分配到small bin中
4. 相邻的free chunk将会被合并成一个更大的fee chunk，增加内存利用率