堆概述

堆的一些基础知识🤪

什么是堆

堆实际上就是程序虚拟地址空间的一块连续的线性区域，它由低地址向高地址方向生长。在程序运行的过程中，堆可以提供动态分配的内存，允许申请大小未知的内存。

你可以把它看成一个结构体数组，数组里每个元素都会开辟一块内存来存储数据，这块用来存储数据的内存就是堆。结构体数组在BSS段上，其内容就是堆的地址，也就是堆的指针。

总的来说，和堆有关的部分被划分为了2块，即管理区块和数据存放区块。数据存放区块就是堆，管理区块可以对堆增删改查，也就是堆管理器。

我们一般称管理堆的那部分程序为堆管理器。堆管理器处于用户程序与内核中间，主要做以下工作：

• 响应用户的申请内存请求，向操作系统申请内存，然后将其返回给用户程序。

  为了保持内存管理的高效性，内核一般都会预先分配很大的一块连续的内存，由内存管理器来通过过某种算法管理这块内存。只有这块堆空间不足时，堆管理器才会再次与操作系统进行交互。

• 管理用户所释放的内存。

  用户释放的内存并不是直接返还给操作系统的，而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的内存的请求。

当前 Linux 使用的堆分配器被称为 ptmalloc2，在 glibc 中实现。

需要注意的是，Linux系统中，只有当真正访问一个地址的时候，系统才会建立虚拟页面与物理页面的映射关系。 也就是说虽然操作系统已经给程序分配了很大的一块内存，但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时，系统才会真正分配物理页面给用户使用。

堆的基本操作

常用命令

heap   #查看堆块
bin    #查看bin区块
p &__free_hook #查看某个函数的真实地址
p *__free_hook #查看某个函数的指向
x/xxgx 0xxxx #查看某个地址的内存
vmmap

malloc

malloc() 是动态内存分配函数。它接收一个参数，即所需分配的内存大小（以字节为单位），并返回指向分配内存起始位置的指针。

void* malloc(size_t size);

• 如果 size =0，将返回当前系统允许的堆的最小内存块（最小值 min 为0x20）
• 如果 size 为负数，由于大部分的系统上 size_t 都是无符号数，所以程序就会分配很大的一块内从空间，但因为系统没有那么多的内存可以分配，通常都会分配失败。
• 如果 malloc() 分配失败，返回的指针将为 NULL。

malloc() 分配的内存空间在使用完后需要手动释放，否则可能导致内存泄漏。

free

free() 是动态内存分配函数。它接受一个参数，即要释放的内存块的起始地址，此函数没有返回值。需要释放的内存空间可能由 malloc()、calloc() 或 realloc() 分配。

void free(void* ptr);

• 当P为空指针，函数并不会执行任何操作
• 当 p 已经被释放之后，再次释放会出现 double free 错误
• 除了被禁用 (mallopt) 的情况，如果是释放一块很大的内存空间，程序会将这块内存空间还给系统，以便减小程序所使用的内存空间。

微观结构

malloc_chunk

在程序的执行过程中，我们称由 malloc 申请的内存为 chunk 。这块内存在 ptmalloc2 内部用 malloc_chunk 结构体来表示。当程序申请的 chunk 被 free 后，会被加入到相应的空闲管理列表中。

无论chunk的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构。但是根据是否被释放，不同的chunk的表现形式会有所不同。

struck malloc_chunk{
    INTERNAL_SIZE_T prev_size;
    INTERNAL_SIZE_T size;
    
    struct malloc_chunk* fd;  
    struct malloc_chunk* bk;
    
    struct malloc_chunk* fd_nextsize;
    struct malloc_chunk* bk_nextsize;
}

• prev_size ：记录前一个较低地址的空闲的 chunk 的大小（包括chunk头）

  当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域无效，所以下一个 chunk 的该部分也可以被当前 chunk 使用，并将其用于扩展当前内存块的可用空间。这就是 chunk 中的空间复用。

• size ：记录的是当前 chunk 的大小，且 size 的大小必须是 2 * SIZE_SZ 的整数倍（32 位系统中，SIZE_SZ 是 4；64 位系统中，SIZE_SZ 是 8）。

  如果申请的内存大小不是 2 * SIZE_SZ 的整数倍，会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。

  该字段的低三个比特位对 chunk 的大小没有影响，它们从高到低分别表示：

  • NON_MAIN_ARENA：记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于

  • IS_MAPPED：记录当前 chunk 是否是由 mmap 分配的。

  • PREV_INUSE：记录前一个 chunk 块是否被分配。

    一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。

物理相邻的两个空闲 chunk 会被合并为一个 chunk 。堆管理器会通过 prev_size 字段以及 size 字段合并两个物理相邻的空闲 chunk 块。

• fd，bk ：两个指针变量，用于构建双向链表，只有 chunk 空闲时才会被使用。

  堆管理器会将其添加到适当的空闲内存块链表中统一管理。在链表中，每个空闲内存块都会有指向前一个内存块和后一个内存块的指针。

  • fd ：指向下一个（非物理相邻）空闲的 chunk
  • bk ：指向上一个（非物理相邻）空闲的 chunk

• fd_nextsize， bk_nextsize ：两个指针变量，和 fd，bk 作用相同，用于较大的 chunk （large chunk）。

  一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。

  • fd_nextsize ：指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。

  • bk_nextsize ：指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。

如果一个 chunk 处于 free 状态，会有两个位置记录其相应的大小：本身的 size 字段和它后一个 chunk 的 prev_size 字段。

已经被分配的chunk结构如下，我们称前两个字段称为 chunk header，后面的部分称为 user data。每次 malloc 申请得到的内存指针，也就是 mem 其实指向 user data 的起始处（这才是用户真正申请到的可利用内存）：

被释放的 chunk 被记录在链表中（可能是循环双向链表，也可能是单向链表）。具体结构如下：

bin

用户释放掉的 chunk 不会马上归还给系统，而是由堆管理器统一管理 heap 和 mmap 映射区域中的空闲的 chunk。空闲的 chunk 我们称之为 bin 。

在实际的实现中，堆管理器采用分箱式方法对空闲的 chunk 进行管理。根据大小将 bin 分为4类：fast bin , small bin , large bin , unsorted bin。在此基础上，每一类 bin 当中内存大小相似的会由双向链表链接，也就是说每类 bin 的内部仍然会有多个互不相关的链表来保存不同大小的 chunk 。

对于 small bins，large bins，unsorted bins 来说，ptmalloc 将它们维护在同一个数组中。这些 bin 对应的数据结构在 malloc_state 中，如下：

#define NBINS 128
mchunkptr bins[ NBINS * 2 - 2 ];

bins 主要用于索引不同 bin 的 fd 和 bk。以 32 位系统为例，bins 前 4 项的含义如下：

下标	0	1	2	3
含义	bin1 的 fd/bin2 的 prev_size	bin1 的 bk/bin2 的 size	bin2 的 fd/bin3 的 prev_size	bin2 的 bk/bin3 的 size

可以看到，bin2 的 prev_size、size 和 bin1 的 fd、bk 是重合的。由于我们只会使用 fd 和 bk 来索引链表，所以该重合部分的数据其实记录的是 bin1 的 fd、bk。虽然后一个 bin 和前一个 bin 共用部分数据，但是其实记录的仍然是前一个 bin 的链表数据。通过这样的复用，可以节省空间。

数组中的 bin 依次如下：

• 第一个是 unsorted bins，这里面的bin都没有进行排序，相对杂乱
• 索引从 2 到 63 的 bin 称为 small bins。同一个链表中的 chunk 大小相等，两个相邻索引的 small bin 链表中的 chunk 大小相差的字节数为 2 个机器字长，即 32 位相差 8 字节，64 位相差 16 字节。
• small bins 后面的 bin 被称作 large bins。large bin 中的每一个 bin 都包含一定范围内的 chunk，其中的 chunk 按 fd 指针的顺序从大到小排列。相同大小的 chunk 同样按照最近使用顺序排列。

Fast bins

有很多的程序都会申请以及释放一些小内存块，如果小内存块释放以后存在与之相邻的空闲的 chunk ，我们将它们进行合并，那么当下一次再次申请相应大小的 chunk 时，就需要再次对 chunk 进行分割，这样就大大降低了堆的利用效率。

为了解决这个问题，ptmalloc 中专门设计了 fast bin，顾名思义它用来快速分配内存。

当用户需要的 chunk 的大小小于 fastbin 的最大值时， 堆管理器会首先判断 fastbin 中相应的 bin 中是否有对应大小的空闲块，如果有的话，就会直接从这个 bin 中获取 chunk。如果没有的话，堆管理器才会进行接下来的一系列操作。

在32位系统中，系统默认的 fast bin 大小为 64 字节，但实际上它可以处理最大 80 字节的数据空间。除此之外，fast bin 可以支持的 bin 的个数为10个，从数据空间为 8 字节开始一直到 80 字节。

fast bins 的特点：

• 采用单向链表对其中的每个 bin 进行组织

• 每个 bin 采取 LIFO 策略，也就是后进先出的方式，最近释放的 chunk 会更早地被分配。

Small bins

small bins 就是 small chunk，当中每个 chunk 的大小与其所在的 bin 的 index 的关系为：chunk_size = 2 * SIZE_SZ *index，具体如下：

下标	2	3	4	5	x	63
SIZE_SZ=4（32 位）	16	24	32	40	2*4*x	504
SIZE_SZ=8（64 位）	32	48	64	80	2*8*x	1008

small bins 的特点：

• 采用双向链表对 bin 进行管理。每个链表都有链表头结点，且每个链表中存储的 chunk 大小都一致。
• 每个 bin 对应的链表采用 FIFO 的规则，也就是先进先出，所以同一个链表中先被释放的 chunk 会先被分配出去。

Large bins

large bins 是用于管理较大内存块的数据结构。

和small bins相同，large bins采用双向链表进行管理，同时采用采用 FIFO 的规则。

Unsorted bin

unsorted bin 是用于管理未分类的空闲内存块的数据结构。当一个内存块被释放时，堆内存管理器会将其添加到 unsorted bin 中，而不是直接合并到其他特定大小范围的 bin 中。

unsorted 的字面意思就是” 不可回收” 的意思，可以看作将不可回收的垃圾（不满足能够进行内存分配的堆块）都放到这个” 垃圾桶” 中。

Top chunk

程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。

其实，所谓的 top chunk 就是处于当前堆的物理地址最高的 chunk 。这个 chunk 不属于任何一个 bin，它的作用在于当所有的 bin 都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就对 heap 进行扩展后再进行分配。

需要注意的是，top chunk 的 prev_inuse 比特位始终为 1，否则其前面的 chunk 就会被合并到 top chunk 中。

Last remainder

在用户使用 malloc 请求分配内存时，ptmalloc2 找到的 chunk 可能并不和申请的内存大小一致，这时候就将分割之后的剩余部分称之为 last remainder chunk ，由 unsorted bin 进行存储。

需要注意的是 top chunk 分割剩下的部分不会作为 last remainder。

宏观结构

arena

arena 是指一块用于管理和分配内存的区域，是内存池的一种。它是堆内存管理的一种组织方式，每个 arena 都是一个独立的内存区域，用于管理特定范围内的内存块。默认情况下，glibc 为每个线程分配一个 arena，以减少不同线程之间的竞争和锁冲突。

main_arena 并不在申请的 heap 中，而是一个全局变量，在 libc.so 的数据段。

需要注意的是，并不是每一个线程都有对应的 arena（使用了系统级的内存分配方式如 mmap() 等，线程可能会绕过 glibc 的内存分配机制，因此没有与 glibc 相关联的 arena；除此之外也可以手动设置限制线程的 arena 创建数量）。

分配规则

• arena: 有一个 main_arena ，是由主线程创建的，thread_arena 则为各线程创建的，当 arena 满了之后就不再创建而是与其他 arena 共享一个 arena，方法为依次给各个 arena 上锁（查看是否有其他线程正在使用该arena），如果上锁成功（没有其他线程正在使用），则使用该 arena ，之后一直使用这个 arena ，如果无法使用则阻塞等待。

• heap：等级比arena要低一些，一个 arena 可以有多个 heap，也是存储了堆相关的信息。

• chunk：分配给用户的内存的一个单位，每当我们分配一段内存的时候其实就是分配得到了一个 chunk ，我们就可以在 chunk 当中进行一定的操作了。不过为了进行动态分配，chunk 本身也有一些数据（元数据），是用来指示其分配等等的数据。

heap_info

当程序刚刚开始运行时，每一个线程是没有自己的 heap 区域的，需要程序主动申请内存。当程序使用完了这个 heap 的资源，就必须要再次申请，并且一般情况下申请的 heap 是不连续的。我们就需要 heap_info这个数据结构来记录不同 heap 之间的链接关系。

typedef struct _heap_info
{
  mstate ar_ptr;                 //对应的arena的地址               
  struct _heap_info *prev;       //上一个 heap_info 的地址   
  size_t size;                   //当前堆的大小        
  size_t mprotect_size;          //堆实际使用的内存大小
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK]; //填充字段，用于对齐 _heap_info 结构体的大小
} heap_info;

特点：

• 使用单向链表进行链接
• 需要确保 MALLOC_ALIGN_MASK+1 对齐，所以可能会用到 pad，

malloc_state

malloc_state 结构用于管理堆，记录每个 arena 当前申请的内存的具体状态，比如说是否有空闲 chunk，有什么大小的空闲 chunk 等等。无论是 thread arena 还是 main arena，它们都只有一个 malloc state 结构。

由于 thread 的 arena 可能有多个，所以它的 malloc state 结构会在最新申请的 arena 中。

struct malloc_state {
    __libc_lock_define(, mutex);            //用于控制程序串行访问同一个分配区,实现访问的互斥锁。
    int flags;                              //标志位，用于记录一些状态信息
    mfastbinptr fastbinsY[ NFASTBINS ];     //fastbin 的空闲块链表,存放每个 fast chunk 链表头部的指针
    mchunkptr top;							//最顶部的内存块，用于指示当前可用的内存位置
    mchunkptr last_remainder;               //最近一次分割的小块内存请求剩余部分的内存块
    mchunkptr bins[ NBINS * 2 - 2 ];        //用于存储 unstored bin，small bins 和 large bins 的 chunk 链表
    unsigned int binmap[ BINMAPSIZE ];      //标识某一个 bin 中是否包含空闲 chunk
    struct malloc_state *next;              //指向下一个 arena 的指针，形成了一个链表结构
    struct malloc_state *next_free;         //指向下一个空闲的 arena 的指针，形成了一个链表结构。
    INTERNAL_SIZE_T attached_threads;       //附加到此 arena 的线程数量
    INTERNAL_SIZE_T system_mem;             //在该 arena 中从系统分配的内存总量
    INTERNAL_SIZE_T max_system_mem;         //在该 arena 中从系统分配的内存的最大值
};

要注意的是，main arena 的 malloc_state 并不是 heap segment 的一部分，而是一个全局变量，存储在 libc.so 的数据段。

内存分配背后的系统调用

我们在程序代码中使用 malloc 函数和 free 函数来申请和分配内存。但实际上与系统交互的并不是这两个函数而是

(s)brk 函数以及 mmap 函数，它们之间的关系如下：

具体的结构如下图（和网上的那些图一样，我重做一张图是因为网上的都是英文，我的英语水平不高看不懂😅）：

要注意的是，并不是所有的 ”堆“ 都在 Heap 区域，mmap 对应 Memory Mapping Segment ，brk 才是对应 Heap 的。

下图为32位程序的虚拟内存结构，64位的虚拟地址大小为8GB，但结构大致相同。

如上图，我们的 malloc 函数是在用户空间对应的 0~3G 的内存进行操作，但用户空间的代码不能直接访问内核空间，因此需要借用 sbrk() 等系统函数充当与内核之间的接口。当然我们也可以直接在用户空间的代码中使用系统调用，进而越过接口直接与系统内核交互，也能达到同样的效果（但是系统调用的效率会相对较低）。

brk 适用于小块内存的分配和释放，而 mmap 适用于大块内存的分配和一些特殊需求（例如映射文件到内存），接下来会进行详细的分析。

我们主要来分析申请堆块的操作

brk 与 sbrk

这两个函数都是通过改变 peogram break （程序中断点）的位置来改变数据段长度，进而实现虚拟内存到物理内存的映射。

brk

brk 通过修改数据段的末尾地址实现内存的分配与回收。它的原型为 void *brk(void *addr); ，其中参数 addr 是新的 Heap 段结束地址。调用 brk 后，操作系统将 Heap 段的结束地址设置为 addr，并将 Heap 段扩展或缩小至新的结束地址。

初始时，堆段的起始地址 start_brk 以及结束位置 brk 指向同一位置，根据程序是否开启了 ASLR保护，位置会有所不同 ：

• 不开 ASLR 保护时， start_brk 以及 brk 会指向 data/bss 段的结尾；
• 开启 ASLR 保护时，start_brk 以及 brk 会指向 data/bss 段后的随机偏移处（两个指针仍指向同一处）

sbrk

sbrk 通过控制间断点向前或向后移动指定长度字节来实现内存的分配与回收。它的原型为 void *sbrk(intptr_t increment);，其中参数 increment 是需要增加或减小的字节数，根据 increment 数值的不同，对应的变化也不相同：

• 当 increment 为正数时，peogram break 会向高地址移动相应的字节数，同样堆的大小会增加相应的字节数，相当于申请内存；
• 当 increment 为负数时，peogram break 会向低地址移动相应的字节数，同样堆的大小会减小相应的字节数，相当于释放内存；
• 当 increment 为 0 时，peogram break 不移动位置，同样函数只返回当前位置。

mmap 与 munmap

mmap 函数是一种内存映射文件的方法，将文件或者其他对象映射到进程的地址空间，实现文件磁盘地址和进程虚拟地址空间中的某一段虚拟地址的一一对应关系。

映射关系一旦建立，就可以直接再内存中对映射的文件进行读写，对应的操作会直接反映在映射的文件上，不用再借用系统调用函数了。

mmap 的函数原型是 void * mmap(void * addr, size_t length,int prot,int flags,int fd,off_t offset); ，其中 length 是指定的映射长度，它并没有严格要求必须填入操作系统分页大小的整数倍，但是操作系统会自动向上取整，确保映射的长度满足对其要求。

munmap 函数用于解除映射关系，其函数原型为 int munmap(void * addr, size_t length); ，addr 为函数返回接收的地址，length 为请求分配的长度。

---

未完待续🤗