什么是堆

在程序运行过程中，堆可以提供动态分配的内存，允许程序申请未知的内存。堆其实就是程序虚拟地址空间的一块连续线性区域，它由低地址往高地址增长。我们称管理堆的那部分程序为：堆管理器

堆管理器位于程序与内核之间，主要做：
1、响应用户申请内存的请求
2、管理用户所释放的内存

目前 Linux 标准发行版中使用的堆分配器是 glibc 的堆分配器：ptmalloc2，主要通过 mallo/free 来分配和释放内存块
不同的线程维护不同的堆称为：per thread arena
主线程创建的堆称为：main arena

glibc 的堆管理实现：
arena 指的是堆内存区域本身，并不是结构；主线程的 main arena 通过 sbrk 创建；其他线程的 arena 通过 mmap 创建
malloc_state 管理 arena 的核心结构，包含堆的状态信息、bins 链表等；main arena 对应的 malloc state 结构存储在 glibc 全局变量中；其他线程 arena 对应的 malloc_state 存储在 arena 本身中
bins 用来管理空闲内存块，通常用链表的结构来进行组织
chunks 内存块结构

在内存分配与使用中只有当真正去访问一个地址的时候，系统才会建立虚拟页面与物理内存的映射关系

image.png
image.png

Arena 头部结构：malloc_state 存储了 arena 的状态，其中的 bins[] 用于管理空闲块的 bins

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;
  /* Flags (formerly in max_fast).  */
  int flags;
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;
  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;
  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];
  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];
  /* Linked list */
  struct malloc_state *next;
  /* Linked list for free arenas.  */
  struct malloc_state *next_free;
  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

主要关心这么几个：
mfastbinptr fastbinsY[NFASTBINS]，保存了 fastbins 各个链表的数组的头，大小为 10 记录的是 fast bin 链
mchunkptr top，指向了 top chunk
mchunkptr bins[NBINS * 2 - 2]，大小为 129。记录的是 unsorted bin（1）、small bin（263）、large bin 链（64126）

堆的基本操作

malloc

malloc(size_t n) size_t 是无符号数
返回对应大小字节的内存块指针，当 n 等于 0 的时候返回的是当前系统允许的堆的最小内存块，当 n 为负数是，程序会去申请很大的内存空间，通常会失败

free

free(void* p)
这个 p 指向的是想要释放的内存块，当 p 为空时，函数不执行任何操作
当 p 被释放后再次释放就会造成 double free
除了被禁用 mallopt 的情况下，当释放了很大的空间时，程序会将这些内存空间还给系统，以便于减少程序所使用的内存空间

内存分配背后的系统调用

前面的无论是 malloc 还是 free，这些函数背后的系统调用主要是 (s)brk 以及 mmap、munmap 函数

(s)brk

对于堆的操作，系统提供 brk 函数，glibc 提供了 sbrk 函数，我们可以通过增加 brk 的大小来向操作系统申请内存

初始时，堆的起始地址 start_brk 以及堆当前末尾 brk 指向同一地址，根据是否开启 ASLR，两者具体位置会有所不同
不开启 ASLR 的时候，start_brk 以及 brk 会指向 data/bss 段的结尾
开启 ASLR 的时候，start_brk 以及 brk 也会指向同一位置，只是这个位置是在 data/bss 段结尾后的随机偏移处

chunk 的结构

我们称由 malloc 申请的内存为 chunk，这块内存在 ptmalloc 中被称为 malloc_chunk 结构体表示

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
  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;
};

prev_size：如果前一个 chunk 是空闲的话，记录物理相邻前一个 chunk 的大小；否则存储前一个的数据
size：该 chunk 的大小，必须是 2*SIZE_SZ 的整数倍，后三位分别是：

  • NON_MAIN_ARENA（A）：表示该 chunk 属于主分配区（1）或者非主分配区（0）
  • IS_MAPPED（M）：记录当前 chunk 是否是由 mmap 分配的，M 为 1 表示该 chunk 是从 mmap 映射区域分配的，否则是从 heap 区域分配的
  • PREV_INUSE（P）：记录前一个 chunk 块是否被分配。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。

fd、bk：chunk 处于分配时从 fd 字段开始就是用户数据了，chunk 空闲时 会被添加到对应的空闲管理链表中

  • fd：指向下一个（非物理相邻）空闲的 chunk
  • bk：指向上一个（非物理相邻）空闲的 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 结构

一个已经分配的 chunk 的样子如下。我们称前两个字段称为 chunk header，后面的部分称为 user data。每次 malloc 申请得到的内存指针，其实指向 user data 的起始处

chunk 指针指向一个 chunk 的开始，一个 chunk 中包含了用户请求的内存区域和相关的控制信息，图中 mem 指针才是真正返回给用户的内存指针。

image.png
image.png

空闲中的 chunk 结构

image.png
image.png

当 chunk 不空闲时，其 M 状态不存在，只有 A P 原本是数据区的地方存储四个指针
指针 fd 指向一个空闲的 chunk，而 bk 指向前一个空闲的 chunk，plmalloc 通过这两个指针将大小相近的 chunk 连成一个双向链表。
对于 large bin 中的空闲 chunk，还有两个指针 fd_nextsize 和 bk_nextsize，这两个指针用于加快 large bin 中查找最近匹配的空闲 chunk 。不同的 chunk 链表又是通过 bins 或者 fastbins 来组织

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

bin

ptmalloc 采用分箱式方法对空闲的 chunk 进行管理。首先，它会根据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类：
fast bins，用于管理较小的 chunk，在之前说的那个 fastbinY 数组里面
small bins，用于管理中等大小的 chunk
large bins，用于管理较大的 chunk
unsorted bin，用于存放未整理的 chunk

bin 对应的数据结构

1
2
3
#define NBINS 128
/* Normal bins packed as described above */
mchunkptr bins[ NBINS * 2 - 2 ];

看不下去