百度工程师带你探秘C++内存管理（ptmalloc篇）
作者 | daydreamer

前篇《探秘C++内存办理（理论篇）》首要介绍了Linux C++程序内存办理的理论基础，本文作为系列文章《探秘C++内存办理》的第二篇，将会探讨经典内存办理器ptmalloc怎么办理C++程序的内存。凭借分析ptmalloc处理问题的着重点和规划完成本钱的权衡，更具体的呈现c++内存办理面临的问题和工程落地中的巧思。

一、概述

ptmalloc是开源GNU C Library(glibc)默许的内存办理器，当时大部分Linux服务端程序运用的是ptmalloc供给的malloc/free系列函数，而它在功用上远差于Meta的jemalloc和Google的tcmalloc。服务端程序调用ptmalloc供给的malloc/free函数恳求和开释内存，ptmalloc供给对内存的集中办理，以尽可能达到：

  • 用户恳求和开释内存更加高效，防止多线程恳求内存并发和加锁

  • 寻求与操作体系交互过程中内存占用和malloc/free功用耗费的平衡点，下降内存碎片化，不频繁调用体系调用函数

简略归纳ptmalloc的内存办理战略：

  • 预先向操作体系恳求并持有一块内存供用户malloc，一起办理已运用和闲暇的内存

  • 用户履行free，会将回收的内存办理起来，并履行办理战略决议是否交还给操作体系

接下来，将从ptmalloc数据结构、内存分配及优缺点介绍最经典的c++内存办理器的完成和运用（以32位机为例）。

二、内存办理

2.1 数据结构

为了处理多线程锁抢夺问题，将内存分配区分为主分配区(main_area)和非主分配区(no_main_area)。一起，为了便于办理内存，对预恳求的内存采用鸿沟标记法划分红许多块(chunk)；ptmalloc内存分配器中，malloc_chunk是基本安排单元，用于办理不同类型的chunk，功用和巨细附近的chunk串联成链表，被称为一个bin。

main_arena与non_main_arena

主分配区和非主分配区形成一个环形链表进行办理， 每一个分配区运用互斥锁完成线程对该分配区的拜访互斥。每个进程只要一个主分配区，但允许有多个非主分配区，且非主分配区的数量只添加不削减。主分配区能够拜访进程的heap区域和mmap映射区域，即主分配区能够运用sbrk()和mmap()分配内存；非主分配区只能运用mmap()分配内存。

百度工程师带你探秘C++内存管理（ptmalloc篇）

关于不同arena的办理战略大致如下：

  • 分配内存

  • 查看该线程的私有变量中是否已经存在一个分配区并对其进行加锁操作，假如加锁成功，则运用该分配区分配内存；假如未找到该分区或加锁失利，遍历环形链表中获取一个未加锁的分配区

  • 假如整个环形链表中没有未加锁的分配区，拓荒一个新的分配区，将其加入循环链表并加锁，运用该分配区满意当时线程的内存分配

  • 开释内存

  • 先获取待开释内存块所在的分配区的锁，假如有其他线程正在运用该分配区，等待其他线程开释该分配区互斥锁后，再开释内存

主分配区和非主分配区的结构如下：

百度工程师带你探秘C++内存管理（ptmalloc篇）

其中fastbinsY和bins是对实践内存块的办理和操作结构：

  • fastbinsY: 用以保存fast bins

  • bins[NBINS * 2 – 2]: unsorted bin（1个，bin[1]）、small bins（62 个，bin[2]~bin[63]）、large bins（63 个，bin[64]~bin[126]）的调集，一共有 126 个表项(NBINS = 128)，bin[0] 和 bin[127] 没有被运用

malloc_chunk与bins

ptmalloc统一办理heap和mmap映射区域中闲暇的chunk，当用户进行分配恳求时，会先企图在闲暇的chunk中查找和分割，然后防止频繁的体系调用，下降内存分配的开销。为了更好的办理和查找闲暇chunk，在预分配的空间的前后添加了必要的控制信息，内存办理结构malloc_chunk的成员及效果如下：

百度工程师带你探秘C++内存管理（ptmalloc篇）

  • mchunk_prev_size: 前一个闲暇chunk的巨细

  • mchunk_size: 当时chunk的巨细

  • 必要的特点标志位：

  • 前一个chunk在运用中(P = 1)

  • 当时chunk是mmap映射区域分配(M = 1)或是heap区域分配(M = 0)

  • 当时chunk归于非主分配区(A = 0)或非主分配区(A = 1)

  • fd和bk: chunk块闲暇时存在，用于将闲暇chunk块加入到闲暇chunk块链表中统一办理

基于chunk的巨细和运用方法，划分出以下几种bins：

百度工程师带你探秘C++内存管理（ptmalloc篇）

  • fast bins

    fast bins仅保存很小的堆，采用单链表串联，增删chunk都发生在链表的头部，进一步提高小内存的分配功率。fast bins记录着巨细以8字节递增的bin链表，一般不会和其他堆块兼并。

  • unsorted bin

    small bins和large bins的缓冲区，用于加速分配的速度，chunk巨细无尺寸约束，用户开释的堆块，会先进入unsorted bin。分配堆块时，会优先查看unsorted bin链表中是否存在适宜的堆块，并进行切开并回来。

  • small bins

    保存巨细 < 512B的chunk的bin被称为small bins。small bins每个bin之间相差8个字节，同一个small bin中的chunk具有相同巨细，采用双向循环链表串联。

  • large bins

    保存巨细 >= 512B的chunk的bin被称为large bins。large bins中的每一个bin别离包含了一个给定范围内的chunk，其中的chunk按巨细降序，相同巨细按时间降序。

当然，并不是一切chunk都按上述的方法来安排，其他常用的chunk，如：

  • top chunk: 分配区的顶部闲暇内存，当bins不能满意内存分配要求的时候，会尝试在top chunk分配。

  • 当top chunk > 用户恳求巨细，top chunk会分为两个部分：用户恳求巨细(user chunk)和剩下top chunk巨细(remainder chunk)

  • 当top chunk < 用户所恳求巨细，top chunk就通过sbrk（main_arena）或mmap（non_main_arena）体系调用来扩容

2.2 内存分配与开释

归纳内存malloc和free的流程大致如下：

内存分配malloc流程

1、获取分配区的锁

2、计算出需求分配的内存的chunk实践巨细

3、假如chunk的巨细 < max_fast，在fast bins上查找适合的chunk；假如不存在，转到5

4、假如chunk巨细 < 512B，从small bins上去查找chunk，假如存在，分配完毕

5、需求分配的是一块大的内存，或许small bins中找不到chunk：

  • a.遍历fast bins，兼并相邻的chunk，并链接到unsorted bin中

  • b.遍历unsorted bin中的chunk：

  • ①能够切开chunk直接分配，分配完毕

  • ②依据chunk的空间巨细将其放入small bins或是large bins中，遍历完成后，转到6

6、需求分配的是一块大的内存，或许small bins和unsorted bin中都找不到适宜的 chunk，且fast bins和unsorted bin中一切的chunk已铲除：

  • 从large bins中查找，反向遍历链表，直到找到第一个巨细大于待分配的chunk进行切开，余下放入unsorted bin，分配完毕

7、检索fast bins和bins没有找到适宜的chunk，判断top chunk巨细是否满意所需chunk的巨细，从top chunk中分配

8、top chunk不能满意需求，需求扩展top chunk：

  • a.主分区上，假如分配的内存 < 分配阈值（默许128KB），运用brk()分配；假如分配的内存 > 分配阈值，运用mmap分配

  • b.非主分区上，运用mmap来分配一块内存

内存开释free流程

1、获取分配区的锁

2、假如free的是空指针，回来

3、假如当时chunk是mmap映射区域映射的内存，调用munmap()开释内存

4、假如chunk与top chunk相邻，直接与top chunk兼并，转到8

5、假如chunk的巨细 > max_fast，放入unsorted bin，而且查看是否有兼并：

  • a.没有兼并状况则free

  • b.有兼并状况而且和top chunk相邻，转到8

6、假如chunk的巨细 < max_fast，放入fast bin，而且查看是否有兼并：

  • a.fast bin并没有改动chunk的状态，没有兼并状况则free

  • b.有兼并状况，转到7

7、在fast bin，假如相邻chunk闲暇，则将这两个chunk兼并，放入unsorted bin。假如兼并后的巨细 > 64KB，会触发进行fast bins的兼并操作，fast bins中的chunk将被遍历兼并，兼并后的chunk会被放到unsorted bin中。兼并后的chunk和top chunk相邻，则会兼并到top chunk中，转到8

8、假如top chunk的巨细 > mmap收缩阈值（默以为128KB），关于主分配区，会企图归还top chunk中的一部分给操作体系

三、优缺点

ptmalloc作为glibc默许的内存办理器，已经广泛的满意大多数大型项目的内存办理，一起它的完成思路也对后来的内存办理器供给了借鉴。

百度工程师带你探秘C++内存管理（ptmalloc篇）

ptmalloc的介绍暂告一段落，接下来的几篇文章将持续探讨高功用内存办理库的集大成者——jemalloc、tcmalloc内存办理库。

———- END ———-

参考资料：

[1] sourceware.org/glibc/wiki/…

[2] sploitfun.wordpress.com/tag/ptmallo…

[3] www.cnblogs.com/biterror/p/…

引荐阅览【技术加油站】系列：

百度工程师教你玩转规划形式（适配器形式）

揭秘百度智能测验在测验评价领域实践

百度工程师带你探秘C++内存办理（理论篇）

从零到一了解APP速度测评

百度工程师教你玩转规划形式（工厂形式）

百度工程师带你探秘C++内存管理（ptmalloc篇）