图解SGI_STL空间配置器原理

简介

STL(Standard Template Library,标准模板库)，实现版本不止一种，例如HP版本、P.J版本、RW版本。

本文主要剖析的是SGI版本的SGL，实现版本详情以及简介此处不过多赘述，可另行搜索了解

STL六大组件相互关系如图

六大容器关系如图中描述，此处对仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数做出例举说明

struct Person
{std::string m_name;int m_age;
};
bool comparePerson(const Person& left, const Person& right)
{return left.m_name == right.m_name && left.m_age == right.m_age;
}
bool comparePersonName(const Person& left, const std::string& right)
{return left.m_name == right;
}
bool comparePersonAge(const Person& left, const int& right)
{return left.m_age == right;
}

std::bind即通用函数适配器，通过适配器指定算法不同的操作方式即可得到不同的结果，即上文提及的仿函数可以协助算法完成不同的策略的变化，如std::find_if绑定的是comparePerson，则查找的必须是人员名称和年龄都需要满足的数据，绑定comparePersonName，则只需要人名相同的数据，绑定comparePersonAge，则查找的是年龄相同的数据。绑定函数不同，即策略的差异性，算法操作会得出不同的结果

SGI空间配置器

接下来就是本文的编写的目的，详细说明SGI空间配置器

1、为什么需要一个空间配置器管理内存（后文若提及内存，和空间配置器是同一概念，空间配置器有点拗口）

直接使用 ::operator new() 和 ::operator delete() 或者 malloc()和free()申请和释放内存会存在以下几个问题：

1.1、小块内存频繁申请释放带来性能问题

申请内存需要和系统交互，系统需要寻找空闲可用的空间，没有合适大小的空间会进行可用空闲空间的碎片的合并等等一系列的操作，这些操作是一种性能上的消耗。

1.2、小块内存带来的内存碎片化问题

过多小块内存申请会创造外部碎片，同时也会导致一页内存中存在内部碎片

1.3、小区块配置时的额外负担

向系统申请到的内存，系统还需要额外的空间来管理内存

2、SGI空间配置器的特殊配置能力-双层级配置能力

所谓双层配置能力指的就是较大片的内存（>128字节）使用一级配置器，即直接使用malloc()和free()申请和释放，对于 <=128字节的内存块使用二级配置器，二级空间配置器会预申请大块内存并分割为小块内存，使用链表的方式管理分割后的小块内存。

2.1第一层空间配置器

_S_oom_malloc(__n)是注册的异常处理函数，例如内存空间不足，申请内存失败的情况下，会执行_S_oom_malloc实现的操作，默认是直接返回异常。

2.2、第二层空间配置器

3、空间配置器分配管理细节剖析（图中列举的函数是SGI源码中的函数, stl_alloc.h）

内存申请流程图如下所示，红色箭头为申请函数入口处执行起始位置，根据源码的条件判断以及处理方案整理出以下流程图，具体细节可以结合后文具体示例的图解和文字描述进行整理流程的梳理。

（1）allocate(size_t __n)函数中首先判断当前申请申请的内存大小（n），当(n>128）时使用一级空间配置器，执行流程 2.1小结图中已展示。

（2）申请(<=128)字节的内存块，即使用的是二级空间配置器

上图为下文图解中各个颜色区域代表的含义简述。

示例1：当前需要申请20字节空间，按照8的倍数向上对齐后即需要获取的内存块大小为24字节，管理24字节大小内存的链表由数组第3个元素记录，以下为示例的主要步骤：

第一步，申请的内存块内存大小对齐后，需要的是24字节，对应数组元素的第三位，此时存储的值为0x0000，表示当前管理的链表为空，即没有可直接取出使用的内存块，此时_S_start_free==_S_end_free说明当前内存池中也没有可以用来分配使用的内存，则需要重新申请大块内存。

第二步：申请内存块的代销缺省值 total_bytes = 24 * 20 = 480字节，_S_heap_size=0，所以此次实际申请一次大块内存的大小bytes_to_get=480字节（计算公式：bytes_to_get=2 * total_bytes + _S_round_up(_S_heap_size >> 4)，图中假设当前通过一级配置器申请的内存起始地址为 0x1000，申请成功的情况下_S_heap_size=480（_S_heap_size+=__bytes_to_get）

第三步：将大块内存分割，共计分割20块大小为24字节的内存块，将第一块地址（0x1000）返回给用户，第2~20块挂载到存储24字节大小的链表管理数组中，此时第三个数组元素值变为第2个内存块的地址（0x1018）,第2个内存块大小为24字节，存储的是第三个内存块的起始地址（0x1030）,按照以上方式会将剩下的19个内存块组成一个链表结构，最后一个内存块的地址即为0x0000。

示例1总结：通过以上三步返回一块用户申请的内存，同时预申请了部分内存，并通过链表管理，下一次申请24字节内存块时，只需要从链表中取出一个内存块返回地址即可。

示例2：在示例1完成的基础上，再次申请一个24字节的内存块，以下为示例的主要步骤：

第一步：检测到管理24字节大小的内存块链表不为空，即可以直接从链表中取出一个内存块返回给用户，优先取出链表中的首个内存块。

第二步：更新链表的指向，需要将数组元素中记录的地址改为取出返回的内存块中的地址（链表结构头删的处理操作，即更改指针指向）

示例3：假设当前申请8字节空间，检测到8字节大小的内存块链表中没有管理可用的空闲内存块，但是当前内存池的中还存在足够缺省申请20个块的内存（内存池空闲空间 > 160字节）可用的空间（即_S_start_free != _S_end_free且 _S_end_free-S_start_free > 160字节）,以下为示例的主要步骤：

第一步：图中当前管理8字节大小的链表为空，即没有可用内存块，而预申请的大块内存池中存在的内存大小为168字节，是可以用于分割为20块8字节的内存块，（注意：此处不要因为曲解示例1，认为每次申请的大块内存刚好是所需字节的20倍，计算公式：bytes_to_get=2 * total_bytes + S_round_up(S_heap_size >> 4中会根据S_heap_size的值得出大块内存申请的预判扩增值，示例1讲述的是初次申请，S_heap_size默认值为0，随着内存的申请，S_heap_size会加上当前申请的大块内存的大小，所以示例1申请完内存后S_heap_size的值为480，后续再次申请会在480基础上增加，因此会出现本例中分配之前以前存在足够的大块内存）。

第二步：如同示例1进行内存块分割，将第一块内存的地址返回给用户，在8字节大小管理链表中追加19个8字节大小内存块进行管理，并更改内存池的起始地址_S_start_free=0x2000，当前内存池中余下8字节的空间。

示例3：假设当前申请120字节空间，检测到管理120字节大小的内存块链表中没有管理可用的空闲内存块（即链表为空），但是当前内存池的中还存在248字节，不够缺省申请的20个内存块总和（20*120字节=2400字节）,但是满足至少一个内存块的申请（内存池空闲空间 < 2400字节）可用的空间

第一步：判断120字节大小的管理链表为空，此时内存池剩余可用内存的大小是248字节，按照默认缺省申请20个内存块，实际需要2400字节，当前剩余内存池内存不够分配，但是可以至少分配一个内存块，因此不需要重新申请内存，可以直接对剩余内存池中内存进行分割。

第二步：首先将内存中的前120字节的内存块（地址：0x3000）地址返回给用户使用，还可用分配出120字节内存块（地址：0x3078）挂载到120字节大小的链表中，此时还余下8字节内存块，不满足120字节的分配，余下的8字节会挂载到管理8字节大小内存块的链表中。（注意：8字节的链表中存在可用内存块，此时新增的内存块会插入链表的首位，内存记录的值更新为原首位内存块的地址）。

示例4：申请8字节大小的内存块，此时管理8字节大小的内存块链表为空，allocate内存也失败的情况下（可以认为系统没有空闲内存提供了），会尝试依次向后查找，较大字节管理的链表是否有挂接的内存块，有则将其还回内存池，再进行分配

第一步：8字节大小内存块链表管理为空，内存池为空，此时通过一级配置器申请160字节失败。依次检查管理16，24，32 … 128字节大小的链表中是否有可用内存块，图中所示最先在管理24字节内存块的链表中检测到可用内存块。

第二步：取出24字节大小内存块管理链表中的第一块内存，此时更新_S_start_free=0x4000，_S_end_free=0x4018，即达到取出一块内存返回内存池的目的。

第三步：将内存池中的内存取出8字节返回给用户，余下的挂载到管理8字节大小内存块的链表中。

4、内存释放

内存释放，如果是大于128字节的内存会代用一级配置中释放接口，实际就是直接free了。如果释放的内存小于128字节，会将其挂接点对应大小块的链表中，假设当前释放一块内存首地址为（0x4000）大小为24字节的内存块，流程如下图所示，会将内存块挂载到对应内存管理链表中

5、总结

上文的示例就是将流程图中的流程具体化的列举分析，可以理解示例后再看下流程图，流程图中的函数名称都是来自源码。
流程如下图所示，会将内存块挂载到对应内存管理链表中

[外链图片转存中…(img-vD9DiqNp-1687711050549)]

5、总结

上文的示例就是将流程图中的流程具体化的列举分析，可以理解示例后再看下流程图，流程图中的函数名称都是来自源码。