内存分配器
GNU Libc的内存分配器(allocator)——ptmalloc(Per Thread Malloc),其源头是Doug Lea的malloc,经Wolfram Gloger改进后能够支持多线程。尽管ptmalloc长期以来因多线程性能欠佳、内存难以回收致使高内存占用等问题而饱受诟病,可它依旧是支持平台最多、应用最为广泛的内存分配器。除此之外,还有其他内存分配器,在链接时能够取代ptmalloc进行内存管理,比如谷歌的tcmalloc、Facebook提出的jemalloc,这些都是针对ptmalloc在多线程场景下的不足进行优化的开源内存分配库。
进程的内存布局
进程的虚拟地址空间以内核空间为边界,内核地址空间在32位系统中占据1GB,仅能在内核态下访问,若用户态直接访问会引发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向操作系统申请内存(使用结束后不会归还给操作系统),非主分配区的数量上限由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_MAXSIZE.
- 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,为避免连续访问空bin可能引发的缺页中断,进而影响分配性能,采用一个64位数来表示bin是否为空。
chunk header数据结构
chunk是malloc实际分配对象所使用的内存片段,除了部分头部信息外,其余空间都用于存放用户数据。在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按照其大小放入对应的bins中。
这样的设计主要是基于局部性原理,旨在让最近释放的内存块优先被考虑用于下一次的分配。
mmap chunk
为了应对超大内存申请的情况,malloc设置了一个阈值,以此来控制缓存的chunk的大小上限。
- 当分配的内存块大小小于等于 DEFAULT_MMAP_THRESHOLD 时,从内存池获取。
- 当分配的内存块大小大于 DEFAULT_MMAP_THRESHOLD 时,直接通过系统调用mmap获取。
DEFAULT_MMAP_THRESHOLD 默认值为128K,在运行时会动态调整(由MIN和MAX两个变量控制调整范围),并且可以进行设置。
通过mmap申请的内存不属于内存池管理,不会进行缓存,释放后会直接归还给操作系统,申请的chunk的M标志位为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
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
small bin是小于512B的chunk的链表。每个链表所保存的chunk size都是相同的,其值等于index * 8。获取small chunk是从链表尾端进行,释放的chunk进入small bins时则放入前端。
large bin
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,将其作为起始选择块:
- 检查该large bin的第一个(最大的)chunk块是否存在,若不存在则跳转到第三步。
- 依次遍历该large bin,找到最接近(大于)或者等于请求大小的chunk,对其进行切分并分配,剩余的chunk则放到unsorted bins中。
- 查找下一个large bin,然后回到第一步。
malloc实现
malloc函数接收一个表示申请内存大小的无符号整数size。在32位系统中,ptmalloc会将分配的内存片大小加上chunk头部后进行8B对齐,后续我们将其称为申请大小或申请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。若合并后的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 bin。
存在的问题
- ptmalloc的内存释放从top-chunk开始,如果与top-chunk相邻的内存一直未释放,会致使其他块都无法释放。在进程中,后申请的内存最好先释放,因此ptmalloc不太适合管理长生命周期的内存。
- 频繁使用mmap系统调用分配内存效率较低。可开启动态调整mmap分配阈值的机制,减少大chunk通过mmap分配的次数。
- 在多线程环境下,需要根据分配区申请锁,在高并发场景中内存消耗较大,并且对于不同生命周期的内存,管理和释放难度较大。
改进方向
- 引入线程级私有缓存。
- 采用整块申请、整块释放策略。
- 利用slab机制,并基于局部性原理优化内存碎片。
总结
这段内容围绕内存分配器展开,重点介绍了 ptmalloc,涵盖其原理、相关数据结构、内存分配和释放机制,分析了存在的问题并给出改进思路,同时对其他内存分配器以及进程内存布局等基础知识也有涉及,为读者全面呈现了内存分配领域的关键知识与技术要点 。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件举报,一经查实,本站将立刻删除。
文章由技术书栈整理,本文链接:https://study.disign.me/article/202511/9.glibc-virtual-memory.md
发布时间: 2025-03-12