堆入门基础
2025-08-09 06:09:35 欧冠世界杯
堆
堆概述
什么是堆
在程序运行过程中，堆可以提供动态分配的内存，允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域，它由低地址向高地址方向增长。我们一般称管理堆的那部分程序为堆管理器。
对于不同的应用来说，由于内存的需求各不相同等特性，因此目前堆的实现有很多种，具体如下
dlmalloc – General purpose allocator
ptmalloc2 – glibc
jemalloc – FreeBSD and Firefox
tcmalloc – Google
libumem – Solaris
目前 Linux 标准发行版中使用的堆分配器是 glibc 中的堆分配器：ptmalloc2。ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。（glibc是最重要的堆管理器）
需要注意的是，在内存分配与使用的过程中，Linux 有这样的一个基本内存管理思想，只有当真正访问一个地址的时候，系统才会建立虚拟页面与物理页面的映射关系。 所以虽然操作系统已经给程序分配了很大的一块内存，但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时，系统才会真正分配物理页面给用户使用。
堆的基本操作
malloc函数
malloc 函数用来动态开辟空间，并返回对应大小字节的内存块的指针。此外，该函数还对一些异常情况进行了处理。
当 n=0 时，返回当前系统允许的堆的最小内存块。当 n 为负数时，由于在大多数系统上，size_t 是无符号数（这一点非常重要），所以程序就会申请很大的内存空间，但通常来说都会失败，因为系统没有那么多的内存可以分配。
free函数
free 函数会释放由 p 所指向的内存块。这个内存块有可能是通过 malloc 函数得到的，也有可能是通过相关的函数 realloc 得到的。此外，该函数也同样对异常情况进行了处理
当 p 为空指针时，函数不执行任何操作。当 p 已经被释放之后，再次释放会出现乱七八糟的效果，这其实就是 double free。除了被禁用 (mallopt) 的情况下，当释放很大的内存空间时，程序会将这些内存空间还给系统，以便于减小程序所使用的内存空间。
堆相关的数据结构
内存分配背后的系统调用
在前面提到的函数中，无论是 malloc 函数还是 free 函数，我们动态申请和释放内存时，都经常会使用，但是它们并不是真正与系统交互的函数。这些函数背后的系统调用主要是 brk函数以及 mmap,munmap函数。
brk函数
对于堆的操作，操作系统提供了 brk 函数，glibc 库提供了 sbrk 函数，我们可以通过增加 brk 的大小来向操作系统申请内存。适用于申请比较小的空间。
初始时，堆的起始地址 start_brk以及堆的当前末尾 brk指向同一地址。动态开辟空间时data段向上扩展，就相当于将heap段的空间划分到data段。
mmap函数
malloc 会使用 mmap来创建独立的匿名映射段。匿名映射的目的主要是可以申请以 0 填充的内存，并且这块内存仅被调用进程所使用。适用于申请比较大的空间。
堆管理器如何工作
arena
操作系统 –> 堆管理器 –> 用户 物理内存 –> arena –> 可用内存
内存分配区，可以理解为堆管理器所持有的内存池（类似输入输出的缓冲区）。堆管理器与内存的交易发生在arena中，arena是一种数据结构用来控制从操作系统申请的数据。
特点：
一个线程只有一个arena，这些arena是互不相同的。主线程的arena称为main_arena，子线程的arena称为thread_arena。并不是是每个线程都有一个arena，其个数是有限制的。
chunk
用户申请内存的单位，也是堆管理器管理内存的基本单位，malloc( )返回的指针指向一个chunk的数据区域。
概述
在程序的执行过程中，我们称由 malloc 申请的内存为 chunk 。这块内存在 ptmalloc 内部用 malloc_chunk 结构体来表示。当程序申请的 chunk 被 free 后，会被加入到相应的空闲管理列表中。无论一个 chunk 的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构。虽然它们使用了同一个数据结构，但是根据是否被释放，它们的表现形式会有所不同。
chunk结构
/* This struct declaration is misleading (but accurate and necessary). It declares a "view" into memory allowing access to necessary fields at known offsets from a given base. See explanation below. */
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;
};
截屏2024-08-14 11.26.32
每个字段的具体的解释如下
prev_size, 如果该 chunk 的**物理相邻的前一地址 chunk（两个指针的地址差值为前一 chunk 大小）**是空闲的话，那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则，该字段可以用来存储物理相邻的前一个 chunk 的数据。这里的前一 chunk 指的是较低地址的 chunk 。size，表示该 chunk 的大小，大小必须是 2 * SIZE_SZ 的整数倍。如果申请的内存大小不是 2 * SIZE_SZ 的整数倍，会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32 位系统中，SIZE_SZ 是 4；64 位系统中，SIZE_SZ 是 8。 该字段的低三个比特位对 chunk 的大小没有影响，它们从高到低分别表示
NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于。IS_MAPPED，记录当前 chunk 是否是由 mmap 分配的。PREV_INUSE，记录前一个 chunk 块是否被分配。如果被设置为 1，则表示前一个 chunk 被分配；如果为 0，则表示前一个 chunk 是空闲的。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。 fd，bk。 chunk 处于分配状态时，从 fd 字段开始是用户的数据。chunk 空闲时，会被添加到对应的空闲管理链表中，其字段的含义如下
fd 指向下一个（非物理相邻）空闲的 chunkbk 指向上一个（非物理相邻）空闲的 chunk通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理 fd_nextsize， bk_nextsize，也是只有 chunk 空闲的时候才使用，不过其用于较大的 chunk（large chunk）。
fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。
**我们称前两个字段称为 chunk header，后面的部分称为 user data。每次 malloc 申请得到的内存指针，其实指向 user data 的起始处。**当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域无效，所以下一个 chunk 的该部分也可以被当前 chunk 使用。这就是 chunk 中的空间复用。
截屏2024-08-14 19.58.55
bin
概述
用户释放掉的 chunk 不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用，降低内存分配的开销。
bin
ptmalloc内存分配步骤
获取分配区的锁，为了防止多个线程同时访问同一个分配区，在进行分配之前需要取得分配区域的锁。线程先查看线程私有实例中是否已经存在一个分配区，如果存在尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，否则，该线程搜索分配区循环链表试图获得一个空闲（没有加锁）的分配区。如果所有的分配区都已经加锁，那么 ptmalloc 会开辟一个新的分配区，把该分配区加入到全局分配区循环链表和线程的私有实例中并加锁，然后使用该分配区进行分配操作。开辟出来的新分配区一定为非主分配区，因为主分配区是从父进程那里继承来的。开辟非主分配区时会调用mmap()创建一个sub-heap，并设置好 top chunk。将用户的请求大小转换为实际需要分配的chunk 空间大小。判断所需分配chunk 的大小是否满足chunk_size <= max_fast (max_fast 默认为 64B)，如果是的话，则转下一步，否则跳到第5 步。首先尝试在fast bins 中取一个所需大小的chunk 分配给用户。如果可以找到，则分配结束。否则转到下一步。判断所需大小是否处在 small bins 中，即判断 chunk_size < 512B 是否成立。如果chunk 大小处在 small bins 中，则转下一步，否则转到第6 步。根据所需分配的 chunk 的大小，找到具体所在的某个 small bin，从该bin 的尾部摘取一个恰好满足大小的 chunk。若成功，则分配结束，否则，转到下一步。到了这一步，说明需要分配的是一块大的内存，或者 small bins 中找不到合适的chunk。 于是， ptmalloc 首先会遍历fast bins 中的 chunk， 将相邻的chunk 进行合并，并链接到unsorted bin 中，然后遍历unsorted bin 中的 chunk，如果 unsorted bin 只有一个chunk，并且这个 chunk 在上次分配时被使用过，并且所需分配的 chunk 大小属于 small bins，并且 chunk 的大小大于等于需要分配的大小，这种情况下就直接将该 chunk 进行切割，分配结束，否则将根据 chunk 的空间大小将其放入 smallbins 或是large bins 中，遍历完成后，转入下一步。到了这一步，说明需要分配的是一块大的内存，或者 small bins 和unsorted bin 中都找不到合适的 chunk，并且fast bins 和unsorted bin 中所有的chunk 都清除干净了。从large bins 中按照“smallest-first，best-fit”原则，找一个合适的 chunk，从中划分一块所需大小的 chunk，并将剩下的部分链接回到 bins 中。若操作成功，则分配结束，否则转到下一步。如果搜索fast bins 和bins 都没有找到合适的 chunk，那么就需要操作top chunk 来进行分配了。判断 top chunk 大小是否满足所需 chunk 的大小，如果是，则从 top chunk 中分出一块来。否则转到下一步。到了这一步， 说明 top chunk 也不能满足分配要求， 所以， 于是就有了两个选择: 如果是主分配区，调用 sbrk()，增加 top chunk 大小；如果是非主分配区，调用 mmap来分配一个新的 sub-heap，增加top chunk 大小；或者使用mmap()来直接分配。在这里，需要依靠 chunk 的大小来决定到底使用哪种方法。判断所需分配的 chunk大小是否大于等于 mmap 分配阈值， 如果是的话， 则转下一步， 调用mmap 分配，否则跳到第12 步，增加 top chunk 的大小。使用mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间。然后将内存指针返回给用户。判断是否为第一次调用 malloc，若是主分配区，则需要进行一次初始化工作，分配21一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。若已经初始化过了，主分配区则调用sbrk()增加heap 空间，分主分配区则在top chunk 中切割出一个chunk，使之满足分配需求，并将内存指针返回给用户。
总结一下：根据用户请求分配的内存的大小，ptmalloc 有可能会在两个地方为用户分配内存空间。在第一次分配内存时，一般情况下只存在一个主分配区，但也有可能从父进程那里继承来了多个非主分配区，在这里主要讨论主分配区的情况，brk 值等于start_brk，所以实际上 heap 大小为 0，top chunk 大小也是 0。这时，如果不增加 heap大小， 就不能满足任何分配要求。 所以， 若用户的请求的内存大小小于mmap 分配阈值，则 ptmalloc 会初始heap。然后在heap 中分配空间给用户，以后的分配就基于这个 heap进行。若第一次用户的请求就大于 mmap 分配阈值，则 ptmalloc 直接使用 mmap()分配一块内存给用户，而 heap 也就没有被初始化，直到用户第一次请求小于 mmap 分配阈值的内存分配。 第一次以后的分配就比较复杂了。简单来说，ptmalloc 首先会查找 fast bins。如果找不到匹配的 chunk，则查找 small bins。若仍然不行，它会合并 fast bins，将 chunk 加入 unsorted bin，并在其中查找。如果还是不成功，它会把 unsorted bin 中的所有 chunk 加入 large bins，然后在其中查找。在 fast bins 和 small bins 中查找时需要精确匹配，而在 large bins 中则遵循"smallest-first，best-fit"原则，不需要精确匹配。若以上方法都失败，ptmalloc 会考虑使用 top chunk。如果 top chunk 也不能满足分配要求，而且所需 chunk 大小大于 mmap 分配阈值，则使用 mmap 进行分配。否则增加heap，增大 top chunk。以满足分配要求。