[STL 学习]: STL的空间配置器
本篇博客大部分内容来自于于侯捷老师的STL源码剖析和一些博客, 仅用作个人的学习记录和日后复习, 如果有博主觉得侵权, 可以联系我删除
文章目录
new / delete 和 ::operator new / ::operator delete
new / delete 是 C++ 表达式, 不是函数, 其内部调用的标准库中的函数原型是
void* operator new(size_t size); //size指明需要分配多少内存
void* operator delete(void *);
new 这个运算符完成两件事 :
- 分配足够的内存, 用来放置某类型的对象;
- 调用一个构造函数, 为刚才分配的内存中的那个对象设定初始值, new 调用 operator new 执行必要的内存分配动作
operator new 只管分配内存, 就像 malloc 那样, 他不知什么是构造函数, 拿到 operator new 分配的内存并将之转换为一个对象是 new 的工作
与之对应的, 使用 delete, 会 :
- 调用对象析构函数,
- 然后使用 operator delete 释放内存
std::alloc
上面说了, new 和 delete 操作都分为两部分, STL allocator 决定将这两阶段操作区分开来:
- 内存配置操作由 alloc::allocate() 负责
- 内存释放操作由 alloc::deallocate() 负责
- 对象构造操作由 ::construct() 负责
- 对象析构由 ::destroy() 负责
construct 和 destroy
construct 接受一个指针 p 和一个初值 value, 该函数将初值设定到指针所指的空间上, placement new (一种对 operator new 的重载)可以完成这一任务destroy 有两个版本, 第一个版本接受一个指针, 调用该指针所指之物的析构函数
第二个版本接收 first 和 last 两个迭代器, 准备将 [first, last] 之间的所有对象析构掉, 会先判断每个对象的析构函数是不是无关痛痒的, 若是就什么也不做, 不是就循环整个范围然后挨个调用析构函数
这部分我了解到这个新东西 placement new
他可以直接调用一个构造函数来初始化一块指定的内存空间
那最近看面经里提到的一个问题 : 如何在共享内存中使用 STL, 是不是这个就是对应的答案? 指定在共享内存中初始化? 重载 operator new, 在共享内存中分配内存, 然后 placement new 就在共享内存中初始化对象
空间的配置与释放
C++ 的内存配置基本操作是::operator new, 内存释放基本操作是 ::operator delete, 这两个全局函数相当于 C 的 malloc 和 free, 而 SGI STL 正是以 malloc 和 free 完成内存的配置和释放的, 而考虑到小内存造成内存碎片, SGI 设计了双层级配置器
第一级配置器:
- 直接使用 malloc 和 free
- 模拟 C++ 的
set_new_handler()实现了一个自己的std::set_new_handler提供给用户显示设置内存不足时的处理函数, 如果内存不足，它会调用一个oom_malloc()函数处理这种情况, 不断尝试释放其他内存, 这个处理函数是要用户自己显式设置的, 没有设置就直接抛出bad_alloc异常, 否则就循环执行回调函数(回调函数中尝试释放内存), 然后malloc, 一直到成功
C++ new_handler 机制是, 你可以要求系统在内存配置需求无法被满足时, 调用一个指定的函数, 就是说, 一旦 ::operator new 无法完成任务, 在丢出 std::bad_alloc 异常之前, 先调用指定的处理流程
二级配置器:
- 维护16个*链表 (free lists) 负责16种小型区块的次配置能力 内存池以 malloc() 配置而得, 如果内存不足, 转调用第一级配置器(那有处理程序)
- 如果需求区块大于 128字节, 就调用第一级配置器
二级配置器以内存池管理, 由 12 个*链表构成, 这16个肩负重任的 free-lists 分别管理大小为 8，16，24，32，40，56，64，72，80，88，96，104，112，120，128字节大小的小额区块(每个链表都是这些对应大小内存区块组成的链表, 比如第一个就是每个节点都是 8 字节内存块的链表)，所以当申请小额内存时，内存的需求量会被上调至 8 的倍数(比如请求30字节, 就会分配32字节)
空间配置函数 allocate()
首先由空间配置函数 allocate() 进行空间的配置，如果能够在 free-lists 中找到对应大小的区块，就把对应的区块拨出，返回。否则就要调用 refill()(这其中又调用了 chunk_alloc() 函数) 对 free-lists 进行填充，新的空间来自内存池，由 chunk_alloc() 完成, 缺省是取得20个新区块，但如果内存池空间不足数量会小于20
static void* allocate(size_t n)
{
//...
// 大于128就调用第一级配置器
if(n > (size_t) __MAX_BYTES)
{
return (malloc_alloc::allocate(n));
}
// 寻找16个free lists中适当的一个
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if(result == 0)
{
// 没找到可用的free list，准备重新填充free list
void* r = refill(ROUND_UP(n));//其中调用chunk_alloc
return r;
}
// 调整free list
*my_free_list = result->free_list_link;
return (result);
}
refile 函数 :(其中调用 chunk_alloc 函数)
template <bool threads,int inst>
void* __default_alloc_template<threads,inst>::refill(size_t n)
{
int nobjs = 20; //默认取得20区块
// 调用chunk_alloc()，尝试取得nobjs个区块作为free list的新节点
// 注意参数nobjs是pass by reference
char* chunk = chunk_alloc(n,nobjs);
obj* volatile * my_free_list;
obj* result;
obj* current_obj,* next_obj;
int i;
// 如果只获得一个区块，这个区块就分配给调用者用，free list无新节点
if(1 == nobjs) return (chunk);
// 否则准备调整free list，纳入新节点
my_free_list = free_list + FREELIST_INDEX(n);
// 以下在chunk空间内建立free list
result = (obj*)chunk;
// 以下引导free list指向新配置的空间
*my_free_list = next_obj = (obj*)(chunk + n);
// 以下将free list的各节点串接起来
for(i = 1; ;i++)
{
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj + n);
if(nobjs - 1 == i)
{
current_obj->free_list_link = 0;
break;
}
else
{
current_obj->free_list_link = next_obj;
}
}
return (result);
}
chunk_alloc() 从内存池是取出新空间可能发生三种情况:
- 内存池剩余量完全满足需求量
- 内存池剩余量不能完全满足需求量，但足够供应 >= 1 个 区块
- 内存池剩余量一个区块都不能供应
内存池:
从内存池中取出空间给 free_list, 由 chunk_alloc 负责
// 申请 nobjs 个大小为size的内存块，
// nobjs传进去的是引用，因为可能会出现内存池空间不够的情况，nobjs最终为最后真实申请到的内存块个数
static char *chunk_alloc(size_t size, int &nobjs)
{
char * result;
size_t total_bytes = size * nobjs;//需要申请空间的大小
size_t bytes_left = end_free - start_free;//计算内存池剩余空间
//如果内存池剩余空间完全满足需求量
if (bytes_left >= total_bytes)
{
result = start_free;
start_free += total_bytes;
return(result);
}
//内存池剩余空间不满足需求量，但是至少能够提供一个以上内存块
else if (bytes_left >= size)
{
nobjs = bytes_left / size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return(result);
}
//剩余空间连一个内存块（大小为size）也无法提供
else
{
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
//内存池的剩余空间分给合适的空闲链表
if (bytes_left > 0)
{
obj * __VOLATILE * my_free_list = free_list + FREELIST_INDEX(bytes_left);
((obj *)start_free) -> free_list_link = *my_free_list;
*my_free_list = (obj *)start_free;
}
start_free = (char *)malloc(bytes_to_get);//配置heap空间，用来补充内存池
if (0 == start_free)
{
int i;
obj * __VOLATILE * my_free_list, *p;
//从空闲链表中找出一个比较大的空闲内存块还给内存池（之后会将这个大的空闲内存块切成多个小的空闲内存块再次加入到空闲链表）
for (i = size; i <= __MAX_BYTES; i += __ALIGN)
{
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (0 != p) //free_list 中有有未用区块
{
*my_free_list = p -> free_list_link;
start_free = (char *)p;
end_free = start_free + i;
return(chunk_alloc(size, nobjs));//递归调用自己，为了修正nobjs
}
}
end_free = 0; //山穷水尽...到处都没有内存可用了
start_free = (char *)malloc_alloc::allocate(bytes_to_get);//调用以及配置器,看看oom机制能否尽点力,这回导致抛异常或者情况得到改善
}
//如果分配成功
heap_size += bytes_to_get;//内存池大小增加
end_free = start_free + bytes_to_get;//修改内存池可用空间的结束位置
return(chunk_alloc(size, nobjs));//递归调用自己，为了修正nobjs
}
}
};
空间释放函数 deallocate()
首先判断区块大小, 如果大于 128字节, 就调用一级配置器 使用 free 释放内存, 小于 128 字节, 就找到对应的 free-list 链表, 将它重新放入该链表 (会插入这个链表头)
static void deallocate(void* p,size_t n)
{
obj* q = (obj*)p;
obj* volatile * my_free_list;
// 大于128就调用第一级配置器
if(n > (size_t) __MAX_BYTES)
{
malloc_alloc::deallocate(p,n);
return;
}
// 寻求对应的free list
my_free_list = free_list + FREELIST_INDEX(n);
// 调整free list，回收区块
q->free_list_link = *my_free_list;
*my_free_list = q;
}
总结
使用 allocate 请求 size 大小的内存空间时
- 如果
size > 128字节, 使用std::alloc的一级配置器 : 直接使用malloc分配内存 - 如果
size < 128字节, 使用二级配置器 :
- 现在空闲链表找对应内存区块大小的链表
- 如果链表不为空, 返回第一个节点(即链表保存的内存区块)
- 如果链表为空, 使用
refile函数为该链表填充新的空间 -
refile函数中调用chunk_alloc函数从内存池中取得新节点(默认是取得20个, 但是内存池空间不足也可能小于20)返回给空闲链表, 如果只拿到一个新节点, 就把这个结点返回给用户, 如果大于一个, 将这些新节点纳入空闲链表, 并将链表头结点返回给用户 - 内存池中如果剩余空间满足需求量(默认的20个), 就返回这些区块;
如果不够但是还能供应>= 1的区块, 就返回这一个, 并且修改以引用方式传进来的请求节点数量, 改为内存池目前能提供的区块量;
如果连一个都没有, 会先检查内存池有没有剩余的其他大小内存块, 有就把他们先编入空闲链表(没有就忽略这一步);
然后首先尝试直接进行malloc补充内存池(malloc 大小为需求量的两倍并加一个随着配置次数越来越大的附加量), 成功后递归调用自己;
如果没有成功就尝试在空闲链表中寻找没有使用的空闲区块, 有就释放, 然后递归调用自己
如果空闲链表中也没有, 那么到这一步已经山穷水尽… 只好尝试使用一级配置器中设置好的oom_malloc()(当然如果用户没有显式设置就直接抛出bad_alloc), 之后继续递归调用自己
- 释放内存, 如果大小超过 128字节, 直接调用
free, 如果小于128字节, 找到存储对应大小的空闲链表, 插入链表头
刚开始初始化内存池时, 内存池和所有空闲链表都是空的, 在用户第一次向内存池请求内存时, 依次执行上述步骤进行首次内存池和空闲链表的填充, 这时其他的空闲链表仍然是空的