2.1 空间配置器的标准接口
根据 STL 规范,以下是 allocator 的标准接口:
allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
allocator::rebind //一个嵌套的模板类,class rebind<U>拥有唯一成员other
//是一个typedef,代表allocator<U>
allocator::allocator()
allocator::allocator(const allocator&)
template<class U>allocator::cllocator<const allocator<U>&) //泛化的拷贝构造
allocator::~allocator()
pointer allocator::address(reference x)const //返回某个对象的地址
const_pointer allocator::address(const_reference x)const //返回某个const对象的地址
//配置空间,足以存储n个T对象,第二个参数是个提示。
pointer allocator::allocate(size_type n, const void* = 0)
void allocator::deallocate(pointer p, size_type n)
size_type allocator::max_size()const //返回可配置的最大容量
//等同于 new((void*)p) T(x)
void allocator::construct(pointer p, const T& x)
//等同于p->~T()
void allocator::destroy(pointer p)
2.2 具备次配置力的 SGI 空间配置器
SGI STL 的配置器与众不同也与规范不同,其名称是alloc
而非allocator
,而且不接受任何参数:
vector<int, std::allocator<int>>iv; //in VC or CB
vector<int, std::alloc>iv; //in GCC
因为 SGI STL 在声明时已经为每个容器都指定了其默认的空间配置器为alloc
,e.g.
template<class T, class Alloc = alloc>
class vector{};
2.2.2 SGI 空间配置器 std::alloc
allocator
只是基层内存配置/释放行为,即::operator new
和::operator delete
的一层薄薄的封装,效率不佳。SGI 采用的实际上是std::alloc
。
- 内存配置由
alloc::allocate()
负责, - 内存释放由
alloc::deallocate()
负责, - 对象构造由
::construct()
负责, - 对象析构由
::destroy()
负责。
2.2.3 构造和析构基本工具
#include <new.h> //欲使用placement new,需先包含此文件
template cclass T1,class T2>
inline void construct ( T1* p, const T2& value) {
new (p)T1(value); //placement new;调用Tl::T1(value) ;
}
//以下是destroy ())第一版本,接受一个指针
template <class T>
inline void destroy (T* pointer) {
pointer->~T ();//调用dtor ~T()
}
//以下是 destroy ()第二版本,接受两个迭代器。
//此函数设法找出元素的数值型别,进而利用_type_traits<>求取最适当措施
template <class ForwardIterator>
inline void destroy (Forwarditerator first,ForwardIterator last){
__destroy (first, last, value_type(first));
}
//判断元素的数值型别(value_type)是否有trivial destructor
template <class ForwardIterator, class T>
inline void__destroy (ForwardIterator first,ForwardIterator last,T*){
typedef typename __type_traits<T> :: has_trivial_destructor trivial_destructor;
__destroy_aux ( first, last, trivial_destructor());
}
//如果元素的数值型别( value type)有non-trivial destructor
template <class ForwardIterator>
inline void
__destroy_aux (Forwardlterator first,ForwardIterator last,_false_type){
for (; first < last ; ++first)
destroy(&*first);
}
//如果元素的数值型别( value type)有trivial destructor
template <class ForwardIterator>
inline void _destroy_aux (ForwardIterator,ForwardIterator,_true_type){}
//以下是destroy ( )第二版本针对迭代器为char*和wchar_t*的特化版
inline void destroy(char* , char* ) { }
inline void destroy ( wchar_t* , wchar_t* ) { }
construct()
接受一个指针 p 和一个初值 value,该函数的用途就是将初值设定到指针所指的空间上,C++的placement new
运算子可以完成这一任务。
destroy()
有两个版本:
- 第一版本:接受一个指针,将该指针所指之物析构掉,直接调用析构函数即可;
- 第二版本:接受
first
和last
两个迭代器,准备将[first, last)范围内的所有对象析构掉。我们不知道该范围有多大,如果范围很大而每个对象的析构函数都是 trivial 的,那么调用这些 trivial 的构造函数效率很低。所以要先利用value_type()
获得迭代器所指对象的型别,再利用__type_traits<T>
判断该型别的析构函数是否 trivial:- 是 trivial 的(__true_type),则什么也不做,空函数体;
- 不是 trivial 的(__false_type),以循环方式遍历整个范围并对每个对象调用第一个版本的
destroy()
。
2.2.4 空间的配置与释放,std::alloc
C++的内存配置和释放基本操作是::operator new
和::operator delete
,相当于 C 的malloc()
和free()
,所以 SGI 以**malloc()**
和**free()**
完成内存的配置和释放。
考虑到小型区块可能造成内存碎片问题,SGI 设计了双层配置器:
- 第一级配置器直接使用
**malloc()**
和**free()**
; - 第二级配置器视情况采用不同策略:
- 当配置区块超过 128 bytes 时,视为足够大,便调用第一级配置器;
- 当配置区块小于 128 bytes 时,视为过小,为了降低额外负担,采用复杂的 memory pool 整理方式。
整个配置器系统设计究竟只开放第一级配置器,或是同时开房第二级配置器,取决于__USE_MALLOC
是否被定义。
无论alloc
被定义为第一级或第二级配置器,SGI 还为它包装了一个接口如下:
template<class T, class Alloc>
class simple_alloc{
public:
static T *allocate (size_t n){
return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T));
}
static T *a1locate (void){
return (T*) Alloc::allocate(sizeof(T));
}
static void deallocate (T *p, size_t n){
if (0 != n)
Alloc::deallocate(p, n*sizeof(T));
}
static void dea11ocate (T *p){
Alloc : :deallocate(p, sizeof(T));
}
};
其内部四个成员其实都是单纯的转调用,调用传递给配置器(可能是一级或二级)的成员函数。该接口使得配置器的配置单位从 bytes 转为个别元素的大小:**sizeof(T)**
。SGI STL 容器全部采用这个simple_alloc
接口:
2.2.5 第一级配置器 __malloc_alloc_template
template<int inst>
class _malloc_alloc_template
{
/* oom_alloc为静态函数成员,用于处理malloc时的内存不足问题
oom_realloc为静态函数成员,用于处理realloc时的内存不足问题
_malloc_alloc_handler为静态数据成员,为void(*)()类型的函数指针,用于用户自
己制定内存分配策略
oom = out-of-memory
*/
static void * oom_malloc(size_t);//out_of_memmory malloc
static void * oom_realloc(void *, size_t);
static void(*_malloc_alloc_oom_handler)();
public:
static void * allocate(size_t n)
{
void * result = malloc(n);//请求内存
if (result == nullptr)//如果内存不足
result=oom_malloc(n);//调用oom_malloc
return result;
}
static void * reallocate(void * p, size_t n)
{
void *result = realloc(n);
if (result == nullptr)
result = oom_realloc(p, n);
return result;
}
static void deallocate(void * p)
{
//使用free函数释放p地址后所分配的内存块
free(p);
}
/*此静态成员函数接受一个void(*)()类型的函数指针作为参数,返回
void(*)()类型的函数指针。其作用为用用户自己定制的内存调度方法替换
_malloc_alloc_handler,由此实现类似C++的set_new_handler方法。
*/
static void(* set_malloc_handler(void(*f)()))()
{
void(*old)() = _malloc_alloc_oom_handler;
_malloc_alloc_oom_handler = f;
return old;
}
};
template<int inst>
void(*_malloc_alloc_template<inst>::_malloc_alloc_oom_handler)() = 0;
template<int inst>
void * _malloc_alloc_template<inst>::oom_malloc(size_t n)
{
void(*my_oom_handler)();
void * result;
//无限循环,直至成功分配内存或用户没有定制内存分配策略
for (;;)
{
my_oom_handler = _malloc_alloc_oom_handler;
if (my_oom_handler == nullptr)//如果用户没有定制内存分配策略
exit(1);
(*my_oom_handler)();//使用用户定制的方法
result = malloc(n);
if (result)
return result;
}
}
template<int inst>
void * _malloc_alloc_template<inst>::oom_realloc(void * p, size_t n)
{
//此函数的设计思路与oom_malloc如出一辙
void(*my_oom_handler)();
void * result;
for (;;)
{
my_oom_handler = _malloc_alloc_oom_handler;
if (my_oom_handler == nullptr)
exit(1);
(*my_oom_handler)();
result = realloc(p,n);
if (result)
return result;
}
}
SGI 以**malloc()**
而非**::operator new**
来配置内存,因为 C++ 并未提供相应于**realloc()**
的内存配置操作。因此 SGI 不能直接使用 C++ 的**set_new_handler()**
在内存配置需求无法被满足的时候调用处理函数,而只能通过函数指针模拟出这一行为。
HINT:SGI 的第一级配置器的allocate()
和realloc()
都是在调用malloc()
和realloc()
不成功后,改调用**oom_malloc()**
和**oom_realloc()**
。后两者内部都有循环,不断调用内存不足处理例程,期望在某次调用之后获得足够的内存完成任务。但是如果客户没有设定内存不足处理例程,这二者就会调用**__THROW_BAD_ALLOC**
,丢出**bad_alloc**
异常信息,或利用**exit(1)**
终止程序。
2.2.6 第二级配置器 __default_alloc_template
第二级配置器增加了一些机制,避免太多小额区块造成内存碎片。配置空间时会有一个额外区块用于管理配置出来的内存,这是无法避免的,但是配置的区块越小,额外区块占比就越大,越显得浪费:
SGI 第二级配置器的做法是:
- 如果区块超过 128 bytes,就移交第一级配置器处理;
如果区块小于 128 bytes时,则以内存池(memory pool)管理,又称次级配置:每次配置一大块内存,并维护对应的 free-list。下次若再有相同大小的内存需求,直接从 free-lists 中拨出。如果释放了小额区块,由配置器回收到 free-lists 中。SGI 第二级配置器会自动将任何小额区块的内心需求量调整为 8 的倍数,并维护 16 个 free-lists,各自管理大小分别为8,16,24, 32, 40, 48, 56, 64, 75, 80, 88, 96, 104, 112, 120,128 bytes 的小额区块。
free-lists 的结构如下:
//一物两用,保存下一个free_list的指针,也保存实际区块的内容
union obj
{
union obj * free_list_link;
char client_data[1];
}
这种实现原理有独特的艺术:由于 free-lists 中维护的是空闲节点,所以一旦被使用(不再空闲)就是以第二行的形式出现,当是空闲的时候就以第一行的形式出现作为链表中的节点(指针)。所以同一时刻只能是二者之一。 ```cpp enum{ALIGN = 8}; //小型区块的上调边界 enum{MAX_BYTES = 128}; //小型区块的上限 enum{NFREELISTS = MAX_BYTES/__ALIGN}; //free-lists 个数
//以下是第二级配置器
//notice:没有”template”类型参数,第二个参数没有派上用处
//第一个参数用于多线程环境下,目前不讨论
template
// chunk allocation state
static char *start_free; //内存池起始位置
static char *end_free; //内存池结束位置
static size_t heap_size;
public:
static void allocate(size_t n);
static void deallocate(void p, size_t n);
static void reallocate(void p, size_t old_sz, size_t new_sz);
};
template
template
template
template
<a name="T9gqI"></a>
## 2.2.7 空间配置函数 allocate()
作为一个配置器,`__default_alloc_template`拥有配置器的标准接口函数`allocate()`。此函数首先判断区块大小,大于 128 bytes 就调用第一级配置器,小于 128 bytes 就检查对应的 free-lists。若有可用区块就拿来用,若没有则将区块大小上调至 8 倍数边界,然后调用`refill()`,准备为 free-lists重新填充空间。
```cpp
static void* allocate(size_t size){
// 如果大于128bytes,交给第一级配置器
if (size > (size_t)__MAX_BYTES){
return malloc_alloc::allocate(size);
}
obj* result = nullptr;
obj* volatile* my_free_list = nullptr;
//寻找 16 个 free-lists 中合适的一个
my_free_list = free_list + FREELIST_INDEX(size);
result = *my_free_list;
if (nullptr == result){
//没有找到合适的,准备重新填充 free-list
void* r = refill(ROUND_UP(size));
return r;
}
// 调整 free-list
*my_free_list = result->free_list_link;
return result;
}
2.2.8 空间释放函数 deallocate()
作为一个配置器,__default_alloc_template
拥有配置器的标准接口函数deallocate()
。首先判断区块大小,大于 128 bytes 就调用第一级配置器,小于 128 bytes 就找出对应的 free-lists,将区块回收
static void deallocate(void* p, size_t n){
if (n > (size_t)__MAX_BYTES){
return malloc_alloc::deallocate(p, n);
}
obj* q = (obj*)p;
obj* volatile* my_free_list = nullptr;
// 寻找相应的free_list
my_free_list = free_list + FREELIST_INDEX(n);
// 头插法,回收区块
q->free_list_link = *my_free_list;
*my_free_list = q;
}
2.2.9 重新填充 free lists
当allocate()
发现 free-lists 中没有可用区块时,就调用**refill()**
,为 free-list 重新填充空间,新的空间将取自内存池(经过**chunk_alloc()**
完成),默认获得 20 个新区块,如果内存池空间不足也可能小于 20。
template<bool threads, int inst>
static void* __default_alloc_template<thread, inst>::refill(size_t n){
int nobjs = 20;
//调用chunk_alloc(),尝试获得nobjs个区块作为free-list的新节点
//注意参数是引用传递
char* chunk = chunk_alloc(n, nobjs);
obj* volatile* my_free_list = nullptr;
obj* result = (obj*)chunk;
obj* current_obj = nullptr;
obj* next_obj = nullptr;
int i = 0;
//如果只获得一个区块,就分配给调用者使用,free-list无新增节点
if (1 == nobjs) return chunk;
//得到不止一个区块,准备调整free-list,纳入新节点
my_free_list = free_list + FREELIST_INDEX(n);
//分配出来的第一个区块要给客户使用,所以返回,然后加上每个区块大小的偏移量,就指向下一个区块了
result = (obj*)chunk;
*my_free_list = next_obj = (obj*)(chunk + n);
for (i = 1; ; ++i){
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj + n);
if (i == nobjs - 1)
{
current_obj->free_list_link = nullptr;
break;
}
current_obj->free_list_link = next_obj;
}
return (result);
}
2.2.10 内存池(memory pool)
chunk_alloc()
负责从内存池中取空间给 free-list 使用:
// 配置一大块空间,可以容纳nobjs个size大小的区块
// 如果配置nobjs个区块有所不便,nobjs会做出相应改变
static char* chunk_alloc(size_t size, int& nobjs){
char* result = nullptr;
// 需要空间的总大小
size_t total_bytes = size * nobjs;
// 内存池剩余空间
size_t bytes_left = end_free - start_free;
// 如果内存池剩余空间满足需要空间
if (bytes_left >= total_bytes){
result = start_free;
start_free = start_free + total_bytes;
return (result);
}else if (bytes_left >= size){
// 如果剩余空间只够1个以上的块(但小于总需求)
//就修正nobjs(得益于传引用)只返回当前能提供的区块数
nobjs = bytes_left / size;
result = start_free;
start_free = start_free + total_bytes;
return result;
}else{
// 如果连一块空间都不够,先声明一个将要向堆区申请的变量
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
// 尝试将剩下的一点点空间再利用
if (bytes_left > 0){
// 将剩余空间配置给合适的free_list
// 声明了一个指针,指向了一个 volatile 指针,该指针指向 obj
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;
}
// 配置heap空间,补充内存池
start_free = (char*)malloc(bytes_to_get);
if (nullptr == start_free){
//堆内存无法满足分配,检查free-lists中有没有空闲节点,将它释放并用作分配
obj* volatile* my_free_list = nullptr;
obj* p = nullptr;
for (int i = size; i <= __MAX_BYTES; i += __ALIGN){
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (nullptr != p){
*my_free_list = p->free_list_link;
start_free = (char*)p;
end_free = start_free + i;
//递归调用自己,以修正nobjs
return chunk_alloc(size, nobjs);
}
}
end_free = 0;//到处都没有内存可用了,调用第一级配置器看oom是否有用
start_free = (char*)malloc_alloc::allocate(bytes_to_get);
}
// 修正内存池的结束位置和总大小
end_free = start_free + bytes_to_get;
heap_size += bytes_to_get;
// 递归调用自己,修正nobjs
return chunk_alloc(size, nobjs);
}
}
e.g. 见图,假设程序一开始,客端就调用chunk_alloc(32,20)
,于是malloc()
配置 40 个 32 bytes区块,其中第 1 个交出,另 19 个交给free_list[3]
维护,余 20 个留给内存池。接下来客端调用chunk_alloc(64,20)
,此时free_list [7]
空空如也,必须向内存池要求支持。内存池只够供应(32*20)/64=
10 个 64 bytes 区块,就把这 10 个区块返回,第 1 个交给客端,余9个由free_list [7]维护。此时内存池全空。接下来再调用chunk_alloc( 96,20)
,此时**free_list[11]**
空空如也,必须向内存池要求支持,而内存池此时也是空的,于是以malloc()
配置 40+n(附加量)个96 bytes区块,其中第 1 个交出,另 19 个交给free_list[11]
维护,余 20+n(附加量)个区块留给内存池
2.3 内存基本处理工具
STL 有五个全局函数作用于未初始化空间上:
construct()
destroy()
uninitialized_copy()
——copy()
uninitialized_fill()
——fill()
uninitialized_fill_n()
——fill_n()
```cpp templateForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);
template
template
三者都可以将**内存配置**与**对象构造行为**分离开。
<a name="Bbzod"></a>
## 2.3.1 uninitialized_fill_n 实现
```cpp
template<class ForwardIterator, class Size, class T>
ForwardIterator uninitialized_fill_n(InputIterator first, Size n, const T& x){
return __uninitialized_fill_n(first, n, x, value_type(first));
}
首先萃取处迭代器first
的value type,然后判断该型别是否是 POD 型别。
POD 型别:Plain Old Data,即标量型别或传统 C struct 型别。
POD 型别必然拥有trivial ctor/dtor/copy/assignment 函数。因此可以针对 POD 型别采用最有效率的初值填写手法,而且 non-POD 型别采取最保险安全的做法:
- 针对 POD 型别:调用高阶函数
fill_n()
; - 针对非 POD 型别:使用循环针对每个变量调用
construct()
->placement new~
2.3.2 uninitialized_copy 实现
大致与uninitialized_fill_n()
相同,只不过在value_type
为 POD 型别时,调用的是copy()
函数。
而且针对**char***
和**wchar_t**
,可以采用最具效率的**memmove()**
直接移动内存内容来执行复制行为,所以针对这两种类型有特化版本。
2.3.3 uninitialized_fill 实现
在value_type
为 POD 型别时,调用的是fill()
函数。
HINT:注意uninitialized_fill()
的两个特化版本中用的是memmove()
而不是memcpy()
。这两者的功效是一样的,区别在于memcpy()
的第二个参数有restrict
限定词(意即memcpy()
假定两块内存区域没有重叠),导致memcpy()
在两个参数有重叠部分时结果不可预知,而memmove()
可以保证完成任务。