- 浏览: 33213 次
- 性别:
- 来自: 大连
-
最新评论
STL容器默认的内存分配器（std::alloc）
STL容器默认的内存分配器（std::alloc）
STL中的容器类的class templates，最后一个template parameter就是alloc，而默认值便是std::alloc。对象构造前的空间配置与对象析构后的空间释放，由<bits/stl_alloc.h>负责，SGI设计此库时，主要有以下几个考虑因素：
- 向heap申请空间
- 考虑线程安全
- 内存不足时的应变措施
- 考虑因“小内存区块”的释放后可能造成的内存碎片（fragment）问题
考虑到当前目标是要了解std::alloc的功能逻辑与实现结构，所以为了简单明了一些，（2.）线程安全先排除不做考虑。
针对（1.）C++有以下两种方式可以配置内存空间。
- ::operator new() 与 ::operator delete();
- malloc() 与 free()；
所以，SGI分别声明了使用方式（1）的new_alloc类和使用方式（2）的malloc_alloc_template模板类。
1. new_alloc
/**
* A new-based allocator, as required by the standard. Allocation and
* deallocation forward to global new and delete. "SGI" style, minus
* reallocate().
* @endmaint
* (See @link Allocators allocators info @endlink for more.)
*/
class __new_alloc
{
public:
static void*
allocate(size_t __n)
{ return ::operator new(__n); }
static void
deallocate(void* __p, size_t)
{ ::operator delete(__p); }
};
2. template<int __inst> class malloc_alloc_template.
/**
* @maint
* A malloc-based allocator.
*/
template <int __inst>
class __malloc_alloc_template
{
private:
static void* _S_oom_malloc(size_t);
static void* _S_oom_realloc(void*, size_t);
static void (* __malloc_alloc_oom_handler)();
public:
static void*
allocate(size_t __n)
{
void* __result = malloc(__n);
if (0 == __result) __result = _S_oom_malloc(__n);
return __result;
}
static void
deallocate(void* __p, size_t /* __n */)
{ free(__p); }
static void*
reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
{
void* __result = realloc(__p, __new_sz);
if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
return __result;
}
static void (* __set_malloc_handler(void (*__f)()))()
{
void (* __old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = __f;
return(__old);
}
};
针对内存碎片的考虑，SGI设计了双层内存配置器，一级配置器就是上述定义两个类中的一个（取决于系统是否定义了宏USE_MALLOC，如果定义了那么使用malloc_alloc_template，否则使用new_alloc。 二级配置器，逻辑上是一个内存池。如果申请的内存大于128字节的话，那么这样申请由一级配置器处理。只有小于128字节的请求会有二级配置器处理。
二级内存配置器（memory pool）的数据结构采用的是freelist的数组，其实这个数据结构实际上就是一个邻接表（表示‘图’的数据结构之一），只是组成数据结构的数据类型所表示的实际意义发生了一些变化。
数组的长度是16（128÷8=16），每个数组元素指向一个freelist头节点，所以memory pool实际上就是16个freelists。每个freelist是一个单链表，单链表中的每个结点代表固定字节数的内存块。比如第一个freelist（数组的头元素指向的freelist），表示由表示容量为8字节的内存块结点组成的单链表。那么按照数组顺序，依次代表的是16，24，32，40，48，56，64，72，80，88，96，104，112，120，128字节的freelist。freelist的节点数据类型是一个union，如下声明。
union obj {
union obj *free_list_link;
char client_data[1];
};
union数据类型具有多面性，按照上述的声明，自然具有两面性了。当节点所代表的内存块属于memory pool中的空闲内存块时，就是free_list_link，指向下一个内存块（像单链表一样）；当节点所代表的内存块已经分配给用户时，就是client_data啦。
memory pool还有两个指针（s_start_free 和 s_end_free) 用于计算空闲内存块的大小，还有size_t的变量heap_size用于记录当前memory pool总容量。memory pool可提供的操作主要是如何根据实际内存请求从memory pool中拨出内存(s_chunk_alloc(size_t size, int& nobjs); )，以及根据内存释放请求归还内存块到memory pool中。
s_chunk_alloc函数是二级内存配置器的核心函数，因为二级配置器default_alloc_template的allocate接口实现都是高度依赖此函数的实现。s_chunk_alloc也是default_alloc_template的业务逻辑核心。
// We allocate memory in large chunks in order to avoid fragmenting the
// malloc heap (or whatever __mem_interface is using) too much. We assume
// that __size is properly aligned. （内存对齐） We hold the allocation lock.
template<bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
int& __nobjs)
{
char* __result; // 预返回的内存块儿首址
size_t __total_bytes = __size * __nobjs;
/* 预分配的内存块总大小，通常情况下nojbs的大小为20,
* nobjs的大小由s_refill函数传进。
*/
size_t __bytes_left = _S_end_free - _S_start_free;
//memory pool剩余内存块大小
if (__bytes_left >= __total_bytes)
/* I: 如果memory pool剩余内存块完全满足需求量 */
{
__result = _S_start_free;
//则将剩余内存块儿的首地址作为结果返回
_S_start_free += __total_bytes;
//将剩余内存块儿的首地址变为增加需求量之后的地址
return(__result);
}
else if (__bytes_left >= __size)
/* II:如果剩余内存空间不足需求量，但是足够供应一个size大小的内存块 */
{
__nobjs = (int)(__bytes_left/__size);
//重新计算nobjs
__total_bytes = __size * __nobjs;
//改变整体预分配内存的大小
__result = _S_start_free;
// 返回分配的内存地址为当前剩余内存的首址
_S_start_free += __total_bytes;
//改变剩余内存的首址为增加了分配内存块后的地址
return(__result);
}
else
/* III：memory pool剩余的空间连一个区块的大小也无法提供 */
{
size_t __bytes_to_get =
2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
/* 扩大需要量， 新需求量是原需求量的二倍与现有内存池大小的四分之一之和 */
if (__bytes_left > 0)
/* 如果内存池还有残余的零头内存，处理零头内存 */
{
_Obj* volatile* __my_free_list =
_S_free_list + _S_freelist_index(__bytes_left);
//寻找监管残余内存的freelist
((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
*__my_free_list = (_Obj*)_S_start_free;
/* 归还那些因不足实际需求大小的内存块到监管的freelist中 */
}
_S_start_free = (char*) __mem_interface::allocate(__bytes_to_get);
// 请求一级内存配置器分配空间
if (0 == _S_start_free)
//如果一级配置器分配失败
{
size_t __i;
_Obj* volatile* __my_free_list;
_Obj* __p;
__i = __size;
for (; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN)
{
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
if (0 != __p)
{
*__my_free_list = __p -> _M_free_list_link;
/* 以下三行比较巧妙，__bytes_left = __i;
* 通过递归调用s_chunk_alloc(size， nobjs)后走II分支
* 找到freelist中未必使用的内存区块，且这个区块足以大于client的实际需求。
*/
_S_start_free = (char*)__p;
_S_end_free = _S_start_free + __i;
return(_S_chunk_alloc(__size, __nobjs));
}
}
/*以上for循环顺次查找每个freelist，看是否还有freelist监管的内存区块未被使用且足够大*/
_S_end_free = 0;
_S_start_free = (char*)__mem_interface::allocate(__bytes_to_get);
/*上述尝试若失败，通过一级配置器抛出bad_alloc异常 */
}
_S_heap_size += __bytes_to_get;
//修改memory pool的总容量
_S_end_free = _S_start_free + __bytes_to_get;
//修改内存池剩余空间大小
return(_S_chunk_alloc(__size, __nobjs));
/* 在一级内存分配器分配了申请的内存后，
* 递归调用s_chunk_alloc后通过I分支处理分配内存。
*/
}
}
根据上述代码，s_chunk_alloc的主要逻辑实际上是处理三种情况：
I: 内存池剩余空间足以满足内存的分配请求（注意此时的接收到的内存分配请求是client需求量的20倍）；
处理方法：直接从剩余空间中拨出需求量大小的内存区块。
II: 内存池剩余空间不足满足需求量，但是大于一个区块（client实际需求量）；
处理方法：缩小需求量至内存池剩余空间按照client实际需求量的最大倍数，然后按照新需求量分配内存块返回；
III: 内存池剩余空间既不能满足需求量，也不能满足实际client需求量；
处理方法：
- 先调整内存池中零头的内存块，使其归为到对应的freelist中。
- 请求一级内存配置器分配扩大后需求量。注意，扩大后的需求量是原始需求量的二倍与内存池大小的四分之一的和那么大。
- 如果一级内存配置器分配新需求量失败，试图在已分配但未使用的内存块（freelist）中寻找足以大于实际client需求的内存分配内存块返回给客户。
- 如果步骤3失败，再向一级内存配置器请求帮助，如果帮助未果则利用一级内存配置器抛出异常bad_alloc。
- 如果一级内存配置器分配请求成功后，递归调用自己走I情况分配内存块。
在了解上述memory pool分配内存块的基本逻辑后，还需要进一步了解s_refill函数。因为二级内存配置器的allocate函数实现是s_refill与s_chunk_alloc两个实现的协作实现。
s_refill模板函数的实现
// Returns an object of size __n, and optionally adds to "size
// __n"'s free list. We assume that __n is properly aligned. We
// hold the allocation lock.
template<bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
int __nobjs = 20;
//默认20个，实际client需求的20倍
char* __chunk = _S_chunk_alloc(__n, __nobjs);
//请求memory pool分配内存块，实际需求的20倍
_Obj* volatile* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
if (1 == __nobjs) return(__chunk);
__my_free_list = _S_free_list + _S_freelist_index(__n);
__result = (_Obj*)__chunk;
//将返回给客户20块内存区块的第一块地址
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
//修改监管freelist的首地址为第一个空闲内存块的地址
for (__i = 1; ; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj*)((char*)__next_obj + __n);
if (__nobjs - 1 == __i) {
__current_obj -> _M_free_list_link = 0;
break;
} else {
__current_obj -> _M_free_list_link = __next_obj;
}
}
//上述for循环，是将freelist中的各结点串接起来。
return(__result);
}
最后我们看看二级内存配置器是如何完成内存配置服务的。
static void*
allocate(size_t __n)
{
void* __ret = 0;
if (__n > (size_t) _MAX_BYTES)
// 如果请求大于128字节，由一级内存配置器分配内存
__ret = __mem_interface::allocate(__n);
else
// 当内存请求小于等于128字节时
{
_Obj* volatile* __my_free_list = _S_free_list
+ _S_freelist_index(__n);
//定位监管的freelist
_Obj* __restrict__ __result = *__my_free_list;
if (__result == 0)
//如果freelist是空的，则通过调用s_refill分配freelist
__ret = _S_refill(_S_round_up(__n));
else
//如果freelist有空闲内存块，则返回一个空闲块给客户
//同时监管freelist的头指针后移一个空闲块
{
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
};
下面举个例子，假设程序一开始，二级内存配置器相继收到如下内存请求：
256字节， 32字节， 32字节，64字节，48字节， 48字节；
1. 256字节：因为其大小大于128字节，则由一级内存配置器直接分配大块内存256字节给客户。
2. 32字节：小于128字节，二级配置器接管请求；找到监管freelist是第4个，数组下标#3， 发现freelist是空；则进一步调用s_refill申请内存；此时s_refill（32）接收到请求后，调用s_chunk_alloc(32, 20)先完成内存池中第四个freelist的分配；
2.1. s_chunk_alloc(32,20)被调用后，内存池是空的，于是直接请求一级内存配置器分配640字节的内存块给内存池。
2.2 一级内存配置器完成分配后，返回给内存池，内存池将此640字节大小的内存块首地址记录到s_start_free指针，同时修改内存池大小，并记录空闲内存块的尾指到s_end_free指针。
2.3 递归调用s_chunk_alloc(32, 20), 此时内存池的空闲内存块是640字节，大于320字节，所以程序处理流程进入I分支。I分支会将这640字节的内存块分成320字节的两大块，前320字节那块作为结果返回，后320字节作为内存池的空闲内存块，s_start_free的地址修改指向后320字节内存块的首地址。
2.4 s_refill此时接收到调用s_chunk_alloc(32, 20)返回的结果后，将320字节内存块分成20块，第一个32字节内存块作为客户请求返回，其余的19个32字节内存块依次串接起来作为第4个freelist监管起来。
3. 32字节：小于128字节，二级配置器接管请求；找到监管freelist是第4个，数组下标#3，发现freelist已分配；此时，直接将freelist中的第一个32字节的内存块（余下19个32字节内存块中的第一个，相当于初始分配的20个内存块中的第二个）返回给客户，同时监管的freelist指向余下的18个内存块。
4. 64字节：小于128字节，二级配置器接管请求。定位监管freelist是第8个，数组下标#7，为空。调用s_refill（64）。同样，s_refill调用s_chunk(64, 20);
4.1. s_chunk_alloc(64, 20)被调用后，内存池的空闲内存块大小是320字节，注意此时需求量是1280字节。
4.2. 因为320字节小于1280字节，但又大于64字节，所以满足II分支的条件。
4.3. II分支先在内存池中修改需求量到320字节，nobjs由原来的20变为5. 将空闲的320字节内存块首址作为结果返回，同时内存池已经没有空闲内存块了。
4.4. 同样，s_refill得到结果后，将320字节的内存块分成5块，第一个64字节内存块作为响应客户的64字节请求返回，而余下的4块串接起来作为第8个freelist监管起来。
5. 48字节：小于128字节，二级配置器接管请求。定位监管freelist是第6个，数组下标#5，为空。调用s_refill(48)。
同样，s_refill调用s_chunk(48,20)。
5.1. s_chunk_alloc(48,20)被调用后，内存池空闲内存块是0字节，需求量是960字节，实际需求是48字节。
5.2. 因为空闲内存块是0字节，所以进入分支III。
5.3. 分支III，请求一级配置器帮助分配1920字节的内存块，但是我们假定现在一级内存配置器分配内存失败。
5.4.1. 此时，分支III从监管48字节的freelist开始，循环随后每一个freelist，略过第8个freelist之前2个空freelist。
5.4.2. 第8个freelist不空，将内存池的空闲内存块设置成freelist监管的4个64字节内存块中的第一个，然后递归调用s_chunk_alloc(48, 20);
5.4.3. 此时内存池空闲内存大小是64字节，走分支II。
5.4.4. 分支II，重新计算nobjs=1。此64字节的内存块的起始地址将作为结果返回，同时修改内存池空闲内存的起始地址到返回结果偏移48字节的地址。所以此时内存池的空闲地址是64-48=16字节。（注意此16字节就是零碎内存块了，这16字节的空闲内存，只有下次内存请求的时候会被归还。）
5.4. s_refill得到结果后，直接将结果再返回给客户。
6. 48字节： 小于128字节，二级配置器接管请求。定位监管freelist是第6个，数组下标#5，为空。调用s_refill(48)。
同样，s_refill调用s_chunk(48,20)。
6.1. s_chunk_alloc(48,20)被调用后，内存池空闲内存是16字节，需求量是960字节，实际需求是48字节。
6.2. 所以走分支III。
6.3. 分支III。
6.3.1. 先将16字节的空闲内存归并到第2个freelist中。（相当于将空闲内存快作为freelist的头元素插入）
6.3.2. 然后请求一级配置器帮助分配1920字节的内存块，但是仍然无功而返
6.3.3. 从第6个freelist开始遍历，略过空freelist，直至第8个freelist。
6.3.4. 第8个freelist不空，将内存池的空闲内存块设置成freelist监管的3个64字节内存块中的第一个，然后递归调用s_chunk_alloc(48, 20);
6.3.5. 此时内存池空闲内存大小是64字节，走分支II。
6.3.6. 分支II，重新计算nobjs=1。此64字节的内存块的起始地址将作为结果返回，同时修改内存池空闲内存的起始地址到返回结果偏移48字节的地址。所以此时内存池的空闲地址是64-48=16字节。
static void
deallocate(void* __p, size_t __n)
{
if (__n > (size_t) _MAX_BYTES)
__mem_interface::deallocate(__p, __n);
else
{
_Obj* volatile* __my_free_list
= _S_free_list + _S_freelist_index(__n);
_Obj* __q = (_Obj*)__p;
__q -> _M_free_list_link = *__my_free_list;
*__my_free_list = __q;
}
}
6.3.7. s_refill得到结果后，直接将结果再返回给客户。
以上便是二级内存配置器的内存分配请求逻辑；下面的deallocate相对来说，就简单至极了。寻找的监管的freelist，然后通过修改指针，归并释放的内存块到监管的freelist即可。注意归还的时候，都是作为freelist的头元素插入到freelist中的。
小结：
感觉freelist的内存分配方式，内存利用率不高。
不知道通过什么方式可以比较一下std::alloc的执行效率 。
发表评论
相关推荐
PaddleTS 是一个易用的深度时序建模的Python库，它基于飞桨深度学习框架PaddlePaddle，专注业界领先的深度模型，旨在为领域专家和行业用户提供可扩展的时序建模能力和便捷易用的用户体验。
白色大气风格的乐器爱好者网站模板下载.zip
海外派遣员工管理守则
flowable-demo-master
内容概要：本文档详细介绍了一个图书馆管理系统的数据库课程设计。内容涵盖需求分析、数据库设计、SQL实现、前端实现及系统测试等环节。项目旨在支持图书借阅、归还、图书信息管理、用户管理等功能。数据库设计包括三个主要表：用户表（Users）、图书表（Books）和借阅记录表（BorrowRecords）。通过具体示例演示了表的创建、数据插入及查询操作。 适用人群：适合正在学习数据库设计或从事数据库相关工作的学生和技术人员。 使用场景及目标：①学习如何进行需求分析，确定系统的功能和数据需求；②掌握数据库设计方法，绘制ER图并转换为具体的表结构；③编写SQL语句，实现数据的增删改查操作；④实现前端页面，完成与后端的交互；⑤进行系统测试，确保各项功能正常运行。 其他说明：此文档不仅提供了理论知识，还给出了详细的代码示例，非常适合动手实践。建议在学习过程中结合文档中的示例，动手实现数据库设计、SQL操作和前端页面，从而加深对数据库技术的理解。
白色风格的手机网站模板下载.rar
白色淡雅风的商务企业网站模板下载.zip
白色大气风格的企业站通用整站网站源码下载.zip
PCle AI加速卡在医疗影像诊断中的应用.docx
Matlab领域上传的视频均有对应的完整代码，皆可运行，亲测可用，适合小白； 1、代码压缩包内容 主函数：main.m； 调用函数：其他m文件；无需运行 运行结果效果图； 2、代码运行版本 Matlab 2019b；若运行有误，根据提示修改；若不会，私信博主； 3、运行操作步骤 步骤一：将所有文件放到Matlab的当前文件夹中； 步骤二：双击打开main.m文件； 步骤三：点击运行，等程序运行完得到结果； 4、仿真咨询 如需其他服务，可私信博主； 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作
白色大气简洁的时装模特企业网站模板下载.zip
西门子PLC 1214C 做的压机控制 可以在触摸屏上任意编辑压装逻辑 该程序为一台设备的完成程序 包含很多工能块 压机控制程序+汇川PN伺服块+脉冲控制块+以太网TCP功能块 + 气缸块+托盘坐标计算块+基恩士扫码器SR1000块+模拟量功能块 所有功能块都是基于模块话编程思路编辑功能块都是SCL语言 可移植性强 一个公式套用所有功能块 可以直接将IO引脚做成触摸屏库关联 编写思路新颖，有助于提高编程能力
通过分析，了解谷歌应用商店app的总体情况。
“开学第一课”小学儿童教育家长会宣传模板
内容概要：本文涵盖了大地测量的基本概念、任务和特点，大地测量系统与参考框架，常用坐标系及其转换方法，传统大地控制网的布设原则，光学经纬仪和全站仪的使用与检验，水平角和三角高程测量的观测方法，以及导线测量的技术要点。文中还提供了多个例题，帮助考生理解和掌握关键知识点。 适合人群：具备一定测绘基础，准备参加注册测绘师资格考试的专业技术人员。 使用场景及目标：用于备考注册测绘师资格考试，提高大地测量领域的专业知识和技能，掌握具体的测量方法和技术细节。 阅读建议：此讲义内容详实，涵盖了大量实用的技术细节，建议结合实际测量工作和练习题进行学习，以加深理解和应用能力。
白色简洁风的设计企业网站模板下载.zip
1、资源项目源码均已通过严格测试验证，保证能够正常运行； 2、项目问题、技术讨论，可以给博主私信或留言，博主看到后会第一时间与您进行沟通； 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用，尤其对于计算机科学与技术等相关专业，更为适合；
白色大气风格的恐龙化石博物馆网站模板下载.zip
白色简洁风格的餐厅会员登录框源码下载.zip
白色创意风格的单反爱好者网站模板下载.zip