PolarDB PostgreSQL版 glibc 虚拟内存管理

内存分配器

GNU Libc 的内存分配器(allocator)—ptmalloc（Per Thread Malloc），起源于Doug Lea的malloc。由Wolfram Gloger改进得到可以支持多线程。虽然ptmalloc一直被诟病多线程性能差、内存无法回收等导致高内存占用等问题，但是它仍是支持平台最多，使用最广泛的内存分配器。此外，还有其他的内存分配器，可以在链接时取代ptmalloc做内存管理，例如谷歌的tcmalloc、Facebook提出的jemalloc，这些都是针对ptmalloc在多线程场景下做了优化的开源内存分配库。

进程的内存布局

进程虚拟地址空间以内核空间为终止，内核地址空间占用1GB（32位系统），仅在内核态下可以访问，用户态直接访问会导致Segmentation Fault。剩下的3GB是用户态的空间，每个用户进程独占所有用户态空间

• Stack：栈，用于保存函数调用时的函数参数、局部变量、寄存器状态和返回地址等

• Mmap：mmap内存映射区，例如动态库、匿名库文件；向下扩展；

• Heap：动态内存分配区，向上扩展

• BSS：未初始化的静态变量，赋零值；

• DATA段：映射数据段，显示初始化的静态变量，即定义时赋值的static

• TEXT段（ELF）：映射的只读数据段，代码段，read-only

虚拟内存管理就是管理堆上以及mmap映射段的内存分配与回收，使得虚拟内存能够合理地提供给用户程序使用。

操作系统提供的内存分配api

用户程序无法直接对堆内存进行使用，而是需要通过系统调用，经过内核分配才能进行使用。

#include <unistd.h>
int brk(void *addr);
void *sbrk(intptr_t increment);

brk()/sbrk()：移动堆顶部的指针brk（start_brk是堆起始地址，brk是堆终止地址），从而增加堆内存范围；

#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

mmap()/munmap()：文件映射，将文件映射到mmap区，

mmap可以实现匿名文件映射，从而给程序中分配用户空间地址。

两种方式都仅仅在虚拟内存的地址空间中分配内存，只有实际访问的时候才会分配物理内存并建立地址转换映射关系（保存在MMU页表中）。

用户态无法直接使用这些特权指令，而是需要通过进程系统调用（systemcall）陷入内核态后才能调用，动态申请内存时较为频繁会导致切换用户态和内核态消耗CPU资源。

因此glibc提出了内存池的设计，将操作系统分配的内存缓存起来，用户申请时先从内存池中取对应的内存块而不直接进行系统调用，缓存的内存不足时才会向内核申请内存。

Ptmalloc2

ptmalloc2是glibc库默认的内存管理库，包含malloc和free接口的实现。

Ptmalloc将数据结构分为三个层次，“arenas”/“heap”，"bin"和“chunk”。

• 每个分配区称之为“arena”；只有一个主分配区，即“main arena”，是由主线程创建的，每个arena都用mutex互斥锁来控制线程并发读写；各个分配区使用循环链表连接；主分配区可以调用sbrk和mmap系统命令，非主分配区只能调用mmap向OS申请内存（使用结束不会归还给os）；非主分配区数量根据CPU核心数定义上限。

• arena中有若干个heap，heap数据结构是专门为从 Memory Mapping Segment 处申请的内存准备的，主分配区中没有该结构；

A heap is a single contiguous memory region holding (coalesceable) malloc_chunks.  It is allocated with mmap() and always starts at an address aligned to HEAP_MAX_SIZE.

• bin是由若干个chunk组成的链表。每个分配区中有固定数量的bins。

• chunk是malloc分配给用户的最小的内存单位，除了头部包含元信息外，其余内存段均用于存放用户数据。

arenas header数据结构

struct malloc_state {
  mutex_t mutex;
  mfastbinptr fastbinsY[NFASTBINS];  /* Fastbins */
  mchunkptr top;/* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr last_remainder;/* The remainder from the most recent split of a small request */
  mchunkptr bins[NBINS * 2 - 2];/* Normal bins packed as described above */
  unsigned int binmap[BINMAPSIZE];/* Bitmap of bins */
  struct malloc_state *next;
  /* ... */
};

每个arena内部都有私有的fastbin以及其他bins，bin是内存片（malloc_chunk）的链表。

多个arena通过链表连接起来，使用mutex互斥量控制多个线程的并发访问arenas，如果没有空闲的arena，则创建新的arena给当前请求的线程；另外，这种锁不可重入。

每个线程都拥有一个 arena 开销过高且意义不大，arena 数量受限于系统核数。main arena 的 arena header 作为一个全局变量，可以在 libc.so 的数据段中找到。其他非主分配区答的header保存在通过sbrk申请的堆段里。

bitmap

64个bins会存在空的bin，因此通过一个64位数来表示bin是否为空，避免连续访问空bin可能导致的缺页中断影响分配性能。

chunk header数据结构

chunk是malloc实际分配对象的内存片段，除了部分header信息外，均用于存放用户数据。在32位系统中头部占用8字节。

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和空闲的chunk数据结构有一些不同。ptmalloc可以通过当前chunk大小和前一个chunk的大小，找到与当前chunk地址相邻的前后两个chunk的地址。

接下来讲讲一些特殊的chunk：

Top chunk

top chunk是arena顶部的一段空闲空间，在主分配区中top chunk顶部是brk指针。top chunk不属于任何bins，当所有的Bin都无法满足分配需求时，会从top chunk中分割分配空间，top chunk底部收缩；

此外，如果当前top chunk可用空间不满足分配需求时，ptmalloc会向操作系统申请内存，将top chunk区域顶部扩张以获取额外的地址空间，这时候才会进行系统调用。主分配区通过调用sbrk()移动brk指针获取空间，非主分配区使用mmap分配空间。

last remainder chunk

unsorted bin用于存放最近释放的small chunk，或者是large bin被切分后剩下的部分，last remainder chunk指向unsorted bin中最后一个chunk。如果当前unsorted bin中仅有一个chunk，即last remainder chunk，那么就会将该chunk分割分配，剩余的部分仍然放在unsorted bin中。如果last remainder chunk都无法分配，那么会清空unsorted bin，将所有chunk根据其size放入对应的bins中。

这样的设计主要是考虑到局部性原理，让最近释放的内存块尽可能被先考虑去做下一次的分配。

mmap chunk

为了应对超大内存申请的情况，malloc设置了一个阈值，用来控制缓存的chunk的大小上限。

• 分配的内存块大小 <= DEFAULT_MMAP_THRESHOLD，从内存池获取

• 分配内存块大小 > DEFAULT_MMAP_THRESHOLD，直接系统调用mmap获取

DEFAULT_MMAP_THRESHOLD 默认是128K，运行时会动态调整（由MIN和MAX两个变量控制调整的范围），可以设置。

mmap申请的内存不属于内存池管理，不会缓存，释放后归还给操作系统。申请的chunkM标志位是1。

内存池设计

在主分配区中，空闲的内存片（chunk）按照其空间大小等放在不同的链表中，这些链表被称为BIN，一共有128个BIN，构成bins数组。

• bins[0]目前没有使用

• bins[1]的链表称为unsorted_list，用于维护free释放的chunk。

• bins[2,63)的区间称为small_bins，用于维护＜512字节的内存块，其中每个元素对应的链表中的chunk大小相同，均为index*8。

• bins[64,127)称为large_bins，用于维护>512字节的内存块，每个元素对应的链表中的chunk大小不同，index越大，链表中chunk的内存大小相差越大，例如: 下标为64的chunk大小介于[512, 512+64)，下标为95的chunk大小介于[2k+1,2k+512)。同一条链表上的chunk，按照从小到大的顺序排列。

除此之外，为了应对更加频繁的小内存申请和利用内存外部碎片空间，引入了fastbin。

fast bin

fastbin一共有10个bin。与上面的bin不同，fastbin是单链表chunk结构（只使用fd），添加和删除chunk都在链表尾部进行（后入先出算法）；fastbin用于保存和分配小于128B的小块内存。

There are 10 such fast bins, covering chunks of size 16, 24, 32, 40, 48, 56, 64, 72, 80, and 88 bytes plus chunk metadata.

即用户释放的小于128B的内存都会先进入fast bin。

unsorted bin

可以存放任意大小的free chunk，用于bins的缓冲区。

• 释放的内存（大于fast bin 最大chunk）会先进入本链表中。

• 此外，在遍历unsorted bin之前，首先会遍历fast bin，如果fastbin没有符合大小的chunk，则将fastbin 中相邻的chunk进行合并，链接到unsorted bin中。

如果申请的size小于unsorted bin中的chunk，切割该chunk分配。

small bin

小于512B的chunk的链表

每个链表保存的chunk size都是一样的，等于index * 8。

获取small chunk是从链表尾端，释放chunk进入small bins放入前端。

large bin

大于等于512字节（小于128K）的chunk，chunk按照大小倒序排列，相同大小的按照最近使用时间排列。

设计

Large bin是glibc库为了应对大块内存分配而建立的缓存；每个large bin中的chunk大小均处于该bin对应的一个动态范围，前32个large bin的size范围是512-544，间隔32字节（64位系统是1024-1087，间隔64字节）；后面的large bin依次间隔翻倍，但是bin数量减半：即后一组16个large bin间隔为64字节。。。

分配

首先根据请求分配内存的大小确定属于哪个large bin，作为起始选择块：

1. 查看large bin第一个（最大的）chunk块是否存在，如果不存在则跳转第三步；

1. 依次遍历large bin，找到最接近（大于）或者等于请求大小的chunk，切分并分配，剩余的chunk放到unsorted bins中。

1. 查找下一个large bin，回到第一步；

malloc实现

malloc会传入一个申请内存size（无符号整数），ptmalloc将分配的内存片大小加上chunk头部进行8B对齐（32位），在后面，我们称之为申请大小或者申请size。

如果申请大小超过MMAP阈值最小值，那么就直接使用mmap分配内存，否则从内存池中申请，内存池的分配策略是先从小的内存链表中以较低的时间复杂度进行查找，依次到更加耗时的系统调用分配。具体分配内存策略如下：

1. 获取分配区的锁

各个分配区中使用mutex互斥锁实现并发控制。首先判断当前线程是否在某个分配区上申请过内存，如果申请过优先在该分配区继续申请。

若所有的分配区的锁都被其他线程占用，则使用mmap创建一个新的非主分配区，设置top chunk；

2. 查找fastbin O(1)

小于128B的申请内存片会先查找fastbin，根据大小定位下标，直接从单链表尾部取对应的chunk

3. 查找small bin O(1)

如果fasterbin中不存在这样的chunk，如果是small bin，根据大小定位对应的bins，如果存在则直接分配。

4. 查找unsorted bin O(n)

• 在unsorted bin中找到第一个大于或等于申请大小的bin，如果链表仅有一个chunk，即last remainder bin，直接分割分配，剩下的留在unsorted bin。

• 若存在多个unsorted bin，那么遍历unsorted bin，将与申请大小不匹配的chunk根据其大小加入small bins或者large bins；

5. 查找large bin O(n)

根据大小定位large bin并遍历链表，找到最小的大于申请大小的chunk，切分并分配，剩下的chunk回到unsorted bin。

6. Top chunk分配 O(1) + 系统调用

如果large bins中没有满足条件的chunk，则从top chunk中切分一部分来分配；

若top chunk不满足分配条件，那么主分配区调用sbrk拓展top，非主分配区调用mmap分配一大块区域，将新top和新区域合并；

图示如下：

fastbin合并

由于可能不断地有chunk被加入到fastbin链表中，因此可能存在较多的小内存碎片，为了缓解这个问题，在新版的ptmalloc2中加入了fastbin chunk合并操作。其原理是，依次遍历fastbin链表的每个chunk，找到chunk的相邻chunk是否空闲，如果前一个chunk是topchunk则该chunk与top chunk合并，如果不是topchunk但是空闲则合并这些chunk，若合并后大于64B则将合并后的大chunk加入unsorted list。chunk合并调用比较频繁，在申请和释放都会进行合并，使得那些相邻小块内存能够合并成大块chunk，降低碎片量，提高利用率。

free原理

• 判断指针是否是NULL

• 判断是否是mmap chunk，如果是，直接释放

• 获取分配区的锁

• 对应的chunk是否与top chunk相邻，如是直接合并

• size是否小于max_fast，如是，放入fastbin；如果size超过合并阈值，启动fastbin合并然后放入unsorted bin。

• 是否属于small bin范围，如是，放入small bin

• 否则放到large

存在的问题

• ptmalloc的释放内存是从top-chunk开始的，如果与top-chunk相邻的内存一直不释放，会导致其他块都不能被释放。进程中后申请内存尽量先释放，因此不适合管理长生命周期的内存。

• 频繁使用mmap系统调用分配内存是低效的，可以开启动态调整mmap的分配阈值机制，来降低大chunk通过mmap分配的次数。

• 多线程下需要根据分配区进行申请锁，高并发场景下内存消耗较大，且对于不同生命周期的内存难以管理和释放。

改进方向

线程级私有缓存；

整块申请、整块释放；

slab机制、局部性原理优化内存碎片；