空间配置器
前言
在STL中，容器的定义中都带一个模板参数，如vector
template <class T, class Alloc = alloc>
class vector {...}
其中第二个参数就是该容器使用的空间配置器，其中缺省使用STL已经实现的空间配置器(alloc)，
该配置器使用malloc/free等为vector分配内存。
#include <vector>
int main()
{
std::vector<int> v;
// Do something;
return 0;
}
- 从用户代码
std::vector<int> v;开始，vector的模板参数class T被替换为int， - 同时第二个模板参数因为没有指定，所以为默认模板参数，即
allocator<int>， - 这个vector对象v会在内部实例一个
allocator<int>的对象，用来管理内存。
假设我们自己写了一个allocator，叫做my_alloc，就可以指定它来为vector分配空间：
allocator 标准接口
这是STL标准要求的allocator必要接口：
// 以下几种自定义类型是一种type_traits技巧，暂时不需要了解
allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference
// 一个嵌套的(nested)class template，class rebind<U>拥有唯一成员other，那是一个typedef，代表allocator<U>
allocator::rebind
allocator::allocator() // 默认构造函数
allocator::allocator(const allocator&) // 拷贝构造函数
template <class U>allocator::allocator(const allocator<U>&) // 泛化的拷贝构造函数
allocator::~allocator() // 析构函数
// 返回某个对象的地址，a.address(x)等同于&x
pointer allocator::address(reference x) const
// 返回某个const对象的地址，a.address(x)等同于&x
const_pointer allocator::address(const_reference x) const
// 配置空间，足以存储n个T对象。第二个参数是个提示。实现上可能会利用它来增进区域性(locality)，或完全忽略之
pointer allocator::allocate(size_type n, const void* = 0)
// 释放先前配置的空间
void allocator::deallocate(pointer p, size_type n)
// 返回可成功配置的最大量
size_type allocator:maxsize() const
// 调用对象的构造函数，等同于 new((void*)p) T(x)
void allocator::construct(pointer p, const T& x)
// 调用对象的析构函数，等同于 p->~T()
void allocator::destroy(pointer p)
上面的标准接口实际只需要关注最后的allocate，deallocate，construct和destroy函数的实现即可
#include <new>
#include <cstddef>
#include <cstdlib>
#include <climits>
#include <iostream>
namespace my_alloc
{
// allocate的实际实现，简单封装new，当无法获得内存时，报错并退出
template <class T>
inline T* _allocate(ptrdiff_t size, T*) {
set_new_handler(0);
T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
if (tmp == 0) {
cerr << "out of memory" << endl;
exit(1);
}
return tmp;
}
// deallocate的实际实现，简单封装delete
template <class T>
inline void _deallocate(T* buffer) { ::operator delete(buffer); }
// construct的实际实现，直接调用对象的构造函数
template <class T1, class T2>
inline void _construct(T1* p, const T2& value) { new(p) T1(value); }
// destroy的实际实现，直接调用对象的析构函数
template <class T>
inline void _destroy(T* ptr) { ptr->~T(); }
template <class T>
class allocator {
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
// 构造函数
allocator(){ return; }
template <class U>
allocator(const allocator<U>& c){}
// rebind allocator of type U
template <class U>
struct rebind { typedef allocator<U> other; };
// allocate，deallocate，construct和destroy函数均调用上面的实际实现
// hint used for locality. ref.[Austern],p189
pointer allocate(size_type n, const void* hint = 0) {
return _allocate((difference_type)n, (pointer)0);
}
void deallocate(pointer p, size_type n) { _deallocate(p); }
void construct(pointer p, const T& value) { _construct(p, value); }
void destroy(pointer p) { _destroy(p); }
pointer address(reference x) { return (pointer)&x; }
const_pointer const_address(const_reference x) { return (const_pointer)&x; }
size_type max_size() const { return size_type(UINT_MAX / sizeof(T)); }
};
} // end of namespace myalloc
**然而，这样并不能通过编译（如果你使用的是GCC编译器），因为SGI STL的allocator并不完全符合STL规范，我们编写的符合规范的自然不能搭配使用，**SGI STL版本的allocator具体实现在下文阐述。
SGI STL 的 allocator
SGI STL 实现了两个allocator：一个是标准的std::allocator，另一个是特殊的std::alloc。
标准配置器 std::allocator
这个allocator部分符合STL标准，它在文件 defalloc.h 中实现。但是SGI STL的容器并不使用它，也不建议我们使用，它存在的意义仅在于为用户提供一个兼容老代码的折衷方法，其实现仅仅是对new和delete的简单包装。
特殊配置器 std::alloc
这个配置器是SGI STL的默认配置器，它在<memory>中实现。
<memory>中包含三个文件：
<stl_construct.h>：定义了全局函数construct()和destroy()，负责对象构造和析构。<stl_alloc.h>：内存配置和释放在此处实现，其内部有两级配置器，第一级结构简单，封装malloc()和free()，第二级实现了自由链表和内存池，用于提升大量小额内存配置时的性能。<stl_uninitialiezed.h>：一些用于用于填充和拷贝大块内存的全局函数。
对象构造和/析构，与内存配置/释放是分离实现的。
用户代码实例化一个vector对象，vector对象调用alloc的接口，注意，不同于之前标准的allocator，这里不需要实例化一个空间配置器，只需要调用alloc的静态函数就行了。
std::alloc的接口与标准非常相似：
static T* allocate()函数负责空间配置，返回一个T对象大小的空间。static T* allocate(size_t)函数负责批量空间配置。static void deallocate(T*)函数负责空间释放。static void deallocate(T*,size_t)函数负责批量空间释放。
我们看到还有两级配置器，上面的接口根据情况调用这两个配置器，第二级配置器实现了内存池和自由链表，当程序多次进行小空间的配置时，可以从内存池和自由链表中获取空间，减少系统调用，提升性能。当进行大空间的配置时，上面的接口直接调用第一级配置器。最终，它们都是用malloc()和free()来配置和释放空间。
一般C++开发者了解到此已经足够应付大多数开发场景了。
这样看起来std::alloc的结构还算清晰，但是实际实现还会出现多种边界情况，比如，当系统调用malloc()空间不足时，我们需要让第一级配置器来处理，这可能涉及从第二级配置器中回收已经缓存但还未使用的空间，事情就变得繁琐了。
缺省的空间配置器
- alloc定义了两级的空间配置器，
- 第一级是对malloc/free简单的封装。
- 而为了解决内存碎片的问题，跟进行内存管理，alloc实现的第二级的空间配置器。
- 第二级空间配置器在分配大块内存(大于128bytes)时，会直接调用第一级空间配置器，
- 而分配小于128bytes的内存时，则使用内存池跟free_list进行内存分配/管理。
第一级空间配置器
- 它可以设定一个处理内存不足的时候的处理函数(跟set_new_handler类似)。
class base_alloc {
public:
// 只是对malloc/free的简单封装
static void* allocate(size_t n)
{
void* res = malloc(n);
if (0 == res) res = oom_malloc(n);
return res;
}
static void* reallocate(void* p, size_t new_sz)
{
void* res = realloc(p, new_sz);
if (0 == res) res = oom_realloc(p, new_sz);
return res;
}
static void deallocate(void* p)
{
free(p);
}
// 用来设置内存不足时的处理函数 该函数参数跟返回值都是一个函数指针
// 一般会抛出异常/尝试回收内存
static void(*set_handler(void(*f)()))()
{
void(*old)() = _oom_handler;
_oom_handler = f;
return old;
}
private:
// 用来处理内存不足的情况
static void* oom_malloc(size_t n)
{
void(*my_handler)();
void* res;
for (;;)
{
my_handler = _oom_handler;
if (0 == my_handler) { return NULL; }
(*my_handler)();
if (res = malloc(n)) return res;
}
}
// 用来处理内存不足的情况
static void* oom_realloc(void* p, size_t n)
{
void(*my_handler)();
void* res;
for (;;)
{
my_handler = _oom_handler;
if (0 == my_handler) { return NULL; }
(*my_handler)();
if (res = reallocate(p, n)) return res;
}
}
// 由用户设置，在内存不足的时候进行处理，由上面两个函数调用
static void(*_oom_handler)();
};
// 处理函数默认为0
void(*base_alloc::_oom_handler)() = 0;
第二级空间配置器
- 该配置器维护一个free_list，这是一个指针数组。
- 在分配内存的时候，补足8bytes的倍数，free_list数组中每个指针分别管理分配大小为8、16、24、32…bytes的内存。
- 下图表示从二级空间配置器中分配内存时是如何维护free_list的(建议参考下面源码阅读)。
- 开始所有指针都为0，没有可分配的区块时(就是free_list[i]==0)会从内存池中分配内存(默认分配20个区块)插入到free_list[i]中。
- 然后改变free_list[i]的指向，指向下一个区块(free_list_link指向下一个区块，如果没有则为0)。
enum { _ALIGN = 8 }; // 对齐
enum { _MAX_BYTES = 128 }; // 区块大小上限
enum { _NFREELISTS = _MAX_BYTES / _ALIGN }; // free-list个数
class default_alloc {
private:
// 将bytes上调到8的倍数
static size_t ROUND_UP(size_t bytes)
{
return (bytes + _ALIGN - 1) & ~(_ALIGN - 1);
}
private:
union obj {
union obj* free_list_link;
char client_data[1];
};
private:
// 16个free-lists 各自管理分别为8,16,24...的小额区块
static obj* free_list[_NFREELISTS];
// 根据区块大小，决定使用第n号free-list
static size_t FREELIST_INDEX(size_t bytes)
{
return (bytes + _ALIGN - 1) / _ALIGN - 1;
}
// 分配内存，返回一个大小为n的区块，可能将大小为n的其他区块加入到free_list
static void* refill(size_t n)
{
// 默认分配20个区块
int nobjs = 20;
char* chunk = chunk_alloc(n, nobjs);
obj** my_free_list;
obj* result, *current_obj, *next_obj;
// 如果只分配了一个区块，直接返回
if (1 == nobjs) return chunk;
// 否则将其他区块插入到free list
my_free_list = free_list + FREELIST_INDEX(n);
result = (obj*)chunk;
// 第一个区块返回 后面的区块插入到free list
*my_free_list = next_obj = (obj*)(chunk + n);
for (int i = 1;; ++i)
{
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj + n);
// 最后一个next的free_list_link为0
if (nobjs - 1 == i)
{
current_obj->free_list_link = 0;
break;
}
current_obj->free_list_link = next_obj;
}
return result;
}
// 分配内存
// 在内存池容量足够时，只调整start_free跟end_free指针
// 在内存池容量不足时，调用malloc分配内存(2 * size * nobjs + ROUND_UP(heap_size >> 4)，每次调整heap_size += 本次分配内存的大小)
static char* chunk_alloc(size_t size, int& nobjs);
static char* start_free; //内存池的起始位置
static char* end_free; //内存池的结束位置
static size_t heap_size; //分配内存时的附加量
public:
static void* allocate(size_t n)
{
obj** my_free_list;
obj* result;
// 大于128就调用第一级空间配置器
if (n > (size_t)_MAX_BYTES)
return base_alloc::allocate(n);
// 寻找适当的free-list
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
// 没有可用的free list
if (result == 0)
return refill(ROUND_UP(n));
// 调整free list 移除free list
*my_free_list = result->free_list_link;
return result;
}
static void deallocate(void* p, size_t n)
{
obj* q = (obj*)p;
obj** my_free_list;
// 大于128就调用第一级空间配置器
if (n > (size_t)_MAX_BYTES)
{
base_alloc::deallocate(p);
return;
}
// 寻找对应的free list
my_free_list = free_list + FREELIST_INDEX(n);
// 调整free list 回收区块(将区块插入到my_free_list)
q->free_list_link = *my_free_list;
*my_free_list = q;
}
static void reallocate(void* p, size_t old_sz, size_t new_sz);
};
char* default_alloc::start_free = 0;
char* default_alloc::end_free = 0;
size_t default_alloc::heap_size = 0;
default_alloc::obj* default_alloc::free_list[_NFREELISTS] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
申请内存和构造分离
主要思想
- 将new的操作分离
- 申请内存
- 调用构造
- 一般情况下，将内存分配和对象构造组合在一起可能会导致不必要的浪费。
标准库allocator类定义在头文件memory中，它帮助我们将内存分配和对象构造分离开来。
它提供一种类型感知的内存分配方法，它分配的内存是原始的、未构造的。
函数
allocator<T> a //定义一个名为a的allocator对象，它可以为类型为T的对象分配内存
a.allocate(n) //分配一段原始的 未构造的 内存，保存n个类型为T的对象
a.deallocate(p,n) //释放内存
a.construct(p,args)//调用构造 arg为构造参数
a.destory(p) //调用析构
使用例子
#include <iostream>
#include <assert.h>
#include <vector>
#include <algorithm>
#include <memory>
using namespace std;
class demo {
public:
demo() {
cout <<"demo con"<<endl;
}
};
int main()
{
std::allocator<A> al;
auto p = al.allocate(1);
al.construct(p);
al.destory(p);
al.deallocate(p,1)
}