The Art of Memory Allocation: Malloc, Slab, C++ STL, and GoLang Memory Allocation

空闲块的组织是个学问,操作系统中常见的空闲块组织的策略分为隐式空闲链表、显式空闲链表、分离的空闲链表三种,现在很多内存分配器中用的最多的还是分离空闲链表居多。

{/collapse-item}
{collapse-item label="2. 经典的Malloc实现" open}
在C语言中，malloc()函数是动态内存分配的基石。这个函数通常使用glibc的ptmalloc2实现。然而，tcmalloc（来自Google）和jemalloc（来自Facebook）等现代分配器在性能和减少内存碎片方面有显著优势，尤其是在多线程环境下。

malloc内存池的实现
2.1 分配的内存大小小于512字节，则通过内存大小定位到small bins对应的index上，大小整除8为索引
2.2 如果对应的bins上有空闲块，返回
2.3 如果对应的bins上没有空闲块，则遍历unsorted list,查找合适大小的空闲块,找到则返回,未找到,将unsorted list中的块归类到small bins和large bins,index++，查找更大的链表，找到则返回，剩下的加入到unsorted list,否则使用top chunk
2.4 如果还未找到空闲块，则会根据需要申请的内存大小来使用分配策略，内存小于128k使用brk，内存大于128k，使用mmap

2.1如果分配内存大小大于512字节，定位到large bins对应的index上，跳到2.2

free
释放的chunk是否与top chunk相邻，相邻则合并
释放的chunk是否与top chunk不相邻，插入到unsorted list
{/collapse-item}
{collapse-item label=" 3. Slab分配器" open}
Slab分配器主要用于内核内存分配，其主要思想是缓存常用对象以减少初始化和销毁成本。Slab分配器通过维护一组预先分配的对象"slabs"来实现这一点，这大大加速了分配过程。

slab分配器高效的解决了内碎和外碎的问题，解决外碎的主要方式是把所有的空闲物理页分组为11块链表，每块链表分别包含大小为1，2，4，8，16...1024个连续的物理页，每个页常规大小是4096(4k)，页帧(物理页)的分配由伙伴系统进行
解决内碎的方式是对于频繁地分配和释放的数据结构，会缓存它，对象析构仅是标记

slab的数据结构如下

高速缓存组(链表),每一个高速缓存里面存储着对象的大小，3个slab链表，每个链表的节点是一个slab,每个slab包含了一个或多个物理页，每个物理页存储着高速缓冲对应的对象大小，每一个高速缓存有三种状态的full、partial、free的slab对象的链表
{/collapse-item}
{collapse-item label="4. C++ STL内存分配器 " open}
C++标准模板库（STL）提供了一套灵活的内存分配器接口。STL内存分配器可以定制，支持不同类型的内存分配策略，这对于优化性能和内存使用非常有用。

c++ stl内存分配器
new
调用operator new配置内存
调用对象构造函数构造对象内容
delete
调用对象析构函数
调用成员的operator delete释放内存

空间分配器
SGI标准的空间配置器
效率不佳，只是将c++的new,delete薄薄的包装了一层
allocate
deallocate
SGI特殊的空间配置器
将new和delete两个阶段的操作分开来
alloc::allocate(num) 为num个元素分配内存
alloc::deallocate(p, num) 回收p所指的“可容纳num个元素”的内存空间
::construct(p, val) 将p所指的元素初始化为val
::destroy(p)/::destroy(first, last) 销毁p所指的元素/销毁迭代器所指的区间

第一级配置器
alloc::allocate(num) 使用malloc分配内存，分配失败则改用oom_malloc， oom_malloc将不断调用客户端设置的内存不足例程，不断尝试释放、配置，如果客户端未设置该函数将抛出异常bad_alloc或利用exit(0)终止程序
alloc::deallocate(p, num) 直接使用free

第二级配置器
次层配置，提升内存管理的效率，减小内存造成的内存碎片问题
分配：

• 分配空间大小超过128bytes时，会使用第一级空间配置器，直接使用malloc relloc free，如果分配不成功则调用句柄释放一部分内存，如果还不能成功则抛出异常
• 分配空间大小小于128bytes时，会使用第二级空间配置器,内存池和空闲链表
  内存池管理：每次配置一大块内存，并且维护对应的16个空闲链表。16个空闲链表分别管理大小为8、16、24...120、128的数据块。
  数据结构
  
  空闲链表节点实现，共用体的形式既可以存储下一个空闲节点又可以存储当前分配给客户使用的数据，当分配给客户时，将不需要记录到空闲链表中
  内存池的开始位置、结束位置
  alloc::allocate(num) 调用将用户申请的字节数扩大到8的倍数，，然后在自由链表中找到对应大小的子链表，找到有内存直接返回空闲链表头结点，空闲链表结点移动到下一个空闲结点，没有找到则调用refill()准备为freelist重新填充空间，新的空间将取自内存池(经由chunk_alloc完成)，chunk_alloc缺省取得20个新节点，，根据内存池开始位置和结束位置来判断容量，但万一内存池空间不足，获得的节点可能小于20.如果块数不够20块，那尽可能的分配最多的块数给自由链表，并且更新每次申请的块数。如果一块都不够则把剩余的内存挂到自由链表，然后向系统heap申请空间，申请的大小为需求量的两倍，再加上一个随着申请次数递增的附加量，如果堆上malloc分配失败，chunk_alloc会从空闲链表中寻找更大的数据块分配给内存池，chunk_alloc递归调用，递归调用山穷水尽之后，则调用一级空间配置器，虽然也是malloc,不过一级空间配置器有out-of-memory处理机制，或许有机会释放一些空间，可以就成功 ，失败就抛出bad_alloc异常
  alloc::deallocate(p, num)
  如果释放的内存大于128bytes时，调用free
  如果释放的内存小于128bytes时，找到合适的自由链表插入

{/collapse-item}
{collapse-item label=" 5. GoLang内存分配实现" open}
GoLang实现了自己的内存分配器，其原理与tcmalloc类似。它维护一块大的全局内存，每个线程（在GoLang中称为P）维护一块小的私有内存。当私有内存不足时，线程会从全局内存申请。

内存结构: GoLang在启动时向系统申请一大块内存，这块内存被划分为spans、bitmap、arena三个部分。arena是堆区，用于分配应用所需内存，而spans和bitmap则用于管理arena区。
Span的角色: Span是内存管理的基本单位，每个span可以包含一个或多个连续的页。为了满足小对象的分配，span中的一页可以进一步划分为更小的单元。对于大对象，可以通过多页span来实现。
Class的分配: GoLang根据对象的大小划分了多个class，每个class代表一个固定大小的对象和每个span的大小。这种分类有助于优化内存分配效率和减少碎片。
mcache和mcentral: GoLang为每个线程分配了span的缓存（mcache），这些缓存的资源来自于全局的mcentral。mcentral管理多个span供线程申请使用。
内存分配过程: 当线程需要内存时，它会首先在mcache中寻找可用的span。如果mcache中没有可用的span，则从mcentral请求。如果mcentral也没有可用的span，则从全局的mheap中申请新的span。

golang程序启动的时候会向系统申请内存如下

预申请的内存划分为spans、bitmap、arena三部分。其中arena即为所谓的堆区，应用中需要的内存从这里分配。
其中spans和bitmap是为了管理arena区而存在的。
arena的大小为512G，为了方便管理把arena区域划分成一个个的page，每个page为8KB,一共有512GB/8KB个页；
spans区域存放span的指针，每个指针对应一个page，所以span区域的大小为(512GB/8KB)*指针大小8byte = 512M
bitmap区域大小也是通过arena计算出来，不过主要用于GC。

span
span是用于管理arena页的关键数据结构，每个span中包含1个或多个连续页，为了满足小对象分配，span中的一页
会划分更小的粒度，而对于大对象比如超过页大小，则通过多页实现。
class
跟据对象大小，划分了一系列class，每个class都代表一个固定大小的对象，以及每个span的大小

// class bytes/obj bytes/span objects waste bytes
// 1 8 8192 1024 0
// 2 16 8192 512 0
// 3 32 8192 256 0
// 4 48 8192 170 32
// ....
// 66 32768 32768 1 0

上表中每列含义如下：
class： class ID，每个span结构中都有一个class ID, 表示该span可处理的对象类型
bytes/obj：该class代表对象的字节数
bytes/span：每个span占用堆的字节数，也即页数*页大小
objects: 每个span可分配的对象个数，也即（bytes/spans）/（bytes/obj）
waste bytes: 每个span产生的内存碎片，也即（bytes/spans）%（bytes/obj）

上表可见最大的对象是32K大小，超过32K大小的由特殊的class表示，该class ID为0，每个class只包含一个对
象。

src/runtime/mheap.go:mspan 定义了其数据结构：

type mspan struct {
  next *mspan //链表前向指针，用于将span链接起来
  prev *mspan //链表前向指针，用于将span链接起来
  startAddr uintptr // 起始地址，也即所管理页的地址
  npages uintptr // 管理的页数
  
  nelems uintptr // 块个数，也即有多少个块可供分配
  
  allocBits *gcBits //分配位图，每一位代表一个块是否已分配
  
  allocCount uint16 // 已分配块的个数
  spanclass spanClass // class表中的class ID
  
  elemsize uintptr // class表中的对象大小，也即块大小
}

cache
有了管理内存的基本单位span，还要有个数据结构来管理span，这个数据结构叫mcentral，各线程需要内存时从
mcentral管理的span中申请内存，为了避免多线程申请内存时不断的加锁，Golang为每个线程分配了span的缓
存，这个缓存即是cache。
src/runtime/mcache.go:mcache 定义了cache的数据结构：

type mcache struct {
  alloc [67*2]*mspan // 按class分组的mspan列表
}

alloc为mspan的指针数组，数组大小为class总数的2倍。数组中每个元素代表了一种class类型的span列表，每
种class类型都有两组span列表，第一组列表中所表示的对象中包含了指针，第二组列表中所表示的对象不含有指
针，这么做是为了提高GC扫描性能，对于不包含指针的span列表，没必要去扫描。
根据对象是否包含指针，将对象分为noscan和scan两类，其中noscan代表没有指针，而scan则代表有指针，需要
GC进行扫描。
mcache和span的对应关系如下图所示：

chache在初始化时是没有任何span的，在使用过程中会动态的从central中获取并缓存下来，跟据使用情况，每种
class的span个数也不相同。上图所示，class 0的span数比class1的要多，说明本线程中分配的小对象要多一
些。

central
cache作为线程的私有资源为单个线程服务，而central则是全局资源，为多个线程服务，当某个线程内存不足时会向central申请，当某个线程释放内存时又会回收进central。
src/runtime/mcentral.go:mcentral 定义了central数据结构：

type mcentral struct {
  lock mutex //互斥锁
  spanclass spanClass // span class ID
  nonempty mSpanList // non-empty 指还有空闲块的span列表
  empty mSpanList // 指没有空闲块的span列表
  
  nmalloc uint64 // 已累计分配的对象个数
}

• lock: 线程间互斥锁，防止多线程读写冲突
• spanclass : 每个mcentral管理着一组有相同class的span列表
• nonempty: 指还有内存可用的span列表
• empty: 指没有内存可用的span列表
• nmalloc: 指累计分配的对象个数

线程从central获取span步骤如下：
5.1 加锁
5.2 从nonempty列表获取一个可用span，并将其从链表中删除
5.3 将取出的span放入empty链表
5.4 将span返回给线程
5.5 解锁

线程将该span缓存进cache
线程将span归还步骤如下：
5.1 加锁
5.2 将span从empty列表删除
5.3 将span加入noneempty列表
5.4 解锁

heap
从mcentral数据结构可见，每个mcentral对象只管理特定的class规格的span。事实上每种class都会对应一个
mcentral,这个mcentral的集合存放于mheap数据结构中。
src/runtime/mheap.go:mheap 定义了heap的数据结构：

type mheap struct {
  lock mutex
  
  spans []*mspan
  
  bitmap uintptr //指向bitmap首地址，bitmap是从高地址向低地址增长的
  
  arena_start uintptr //指示arena区首地址
  arena_used uintptr //指示arena区已使用地址位置
  
  central [67*2]struct {
    mcentral mcentral
    pad [sys.CacheLineSize - unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
  }
}

• lock： 互斥锁
• spans: 指向spans区域，用于映射span和page的关系
• bitmap：bitmap的起始地址
• arena_start: arena区域首地址
• arena_used: 当前arena已使用区域的最大地址
• central: 每种class对应的两个mcentral

从数据结构可见，mheap管理着全部的内存，事实上Golang就是通过一个mheap类型的全局变量进行内存管理的。
mheap内存管理示意图如下：

内存分配的过程
针对待分配对象的大小不同有不同的分配逻辑：
(0, 16B) 且不包含指针的对象： Tiny分配
(0, 16B) 包含指针的对象：正常分配
[16B, 32KB] : 正常分配
(32KB, -) : 大对象分配其中Tiny分配和大对象分配都属于内存管理的优化范畴，这里暂时仅关注一般的分
配方法。
以申请size为n的内存为例，分配步骤如下：

• 获取当前线程的私有缓存mcache
• 跟据size计算出适合的class的ID
• 从mcache的alloc[class]链表中查询可用的span
• 如果mcache没有可用的span则从mcentral申请一个新的span加入mcache中
• 如果mcentral中也没有可用的span则从mheap中申请一个新的span加入mcentral
• 从该span中获取到空闲对象地址并返回
  {/collapse-item}
  {collapse-item label=" 6. 总结 " open}
  每种内存分配器都有其独特的设计理念和优化策略。了解这些不同实现的原理不仅对深入理解语言和环境的内存管理有帮助，也对编写高效且资源友好的代码至关重要。

本篇博客提供了一个概览，介绍了多种内存分配器的设计和实现。从经典的malloc到现代语言如GoLang的内存管理，我们看到了内存分配技术的演进和优化。希望这篇文章能为你在内存管理方面的深入学习提供一个坚实的起点。
{/collapse-item}