空间配置器
SGI STL有2个种空间配置器:
std::allocator
,符合STL标准,但很少使用,也不建议使用。因为只是把::operator new
和::operator delete
做了一层薄薄封装,效率差。
std::alloc
,SGI特殊空间配置器,将配置器分为两级,兼顾了效率与内存碎片问题,效率高。推荐使用。
下面主要讲的也是std::alloc
。
一般而言,我们所习惯的C++内存配置操作和释放是这样的:
1 2 3
| class Foo { ... }; Foo* f = new Foo(); delete f;
|
其中new
算式内涵两阶段操作:
- 调用
::operator new
配置内存
- 调用
Foo::Foo()
构造对象内容
delete也有两阶段操作
- 调用
Foo::~Foo()
将对象析构
- 调用
::operator delete
释放内存
为了精密分工,STL allocator决定将这两阶段操作区分开来。
- 内存配置由
alloc::allocate()
负责,内存释放由alloc::deallocate()
负责。(头文件<stl_alloc.h>)
- 对象构造由
::construct()
负责,对象析构由::destroy()
负责。(头文件<stl_construct.h>)
头文件说明
STL标准规定,配置器定义于,而SGI 内含3个与配置器相关的文件:
- <stl_construct.h> 定义了全局函数construct(), destroy(), 负责对象的构造和析构。隶属于STL标准规范。
- <stl_alloc.h> 定义了一、二级配置器,彼此合作。配置器名为alloc。
- <stl_uninitialized.h> 定义一些全局函数,用来填充(fill)或复制(copy)大块内存数据。比如函数
un_initialized_copy()
、un_initialized_fill()
、un_initialized_fill_n()
。
构造和析构工具:construct, destroy
全局函数construct(), destroy()在已配置内存的基础上,用于对象的构造和析构。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| template <class T> inline void _Construct(T1* p) { new ((void*) p) T(); }
template<class T1, class T2> inline void construct(T1* p, const T2& value) { new (p) T1(value); }
template<class T> inline void destroy(T* pointer) { pointer->~T(); }
template<class ForwardIterator> inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) { for (; first < last; ++first) destroy(&*first); }
template<class ForwardIterator> inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __true_type) { }
|
代码中一组__destroy()
是辅助实现destroy()
的,编译器会在编译期根据萃取出参数的类型(value type)。接着萃取出trivial_destructor特性,判断是否支持trivial_destructor
(平凡的析构函数,说明没有申请动态内存),如果支持(特性为__true_type),就不需要专门调用析构函数;如果不支持(特性为__false_type),就需要针对迭代器区间每个元素,逐个调用析构函数。如果迭代器区间包含元素较多,这能节省不少时间。
当一个类的析构函数不需要做任何额外的工作时,我们称这个类的析构函数为trivial destructor,STL中有一个 has_trivial_destructor函数,这是编译器内置的,用来检测类型是否拥有用户自定义的析构函数。
空间的配置与释放
std::alloc 负责内存的配置和释放。对象构造前的空间配置和对象析构后的空间释放,由<stl_alloc.h>负责
C++的内存配置基本操作::operator new()
,内存释放基本操作::operator delete()
。这2全局函数相当于C的malloc()
和free()
。SGI正是以malloc()
和free()
完成内存的配置与释放的,但SGI STL的std::alloc
不能使用new/delete,因为new/delete会直接构造/析构对象,而这不符合std::alloc
职责。
operator new只分配所要求的空间,不调用相关对象的构造函数。
std::alloc设计的基本思想
为避免小型区块可能造成的内存碎片问题,SGI STL设计了双层级配置器:
- 第一级配置器,直接使用
malloc()
, free()
;
- 第二级配置器,视情况采用不同策略:
当配置区块 > 128bytes时,视为“足够大”,便调用第一级配置器;
当配置区块 <= 128bytes时,视为“过小”,交给memory pool(内存池)来管理,不再求助于第一级配置器。
设计可以只开放第一级配置器,可以同时开启。
SGI STL的两级配置器:__malloc_alloc_template
是第一级配置器,__default_alloc_template
是第二级配置器。
SGI STL容器全部使用这个simple_alloc接口。例如,vector的专属空间配置器data_allocator,就是simple_alloc<value_type, Alloc>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
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* allocate(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 deallocate(T* p) { Alloc::deallocate(p, sizeof(T)); } };
|
第一级配置器:__malloc_alloc_template
- allocate() 直接使用malloc(), deallocate() 直接使用free();
- 模拟C++的set_new_handler()以处理内存不足的状况。
如何选择使用哪个配置器
定义或取消宏__USE_MALLOC,就能决定alloc的实际类型(一级配置器 or 二级配置器)。SGI STL并未定义__USE_MALLOC,因此SGI默认使用的二级配置器。
1 2 3 4 5 6 7 8 9 10 11
| # ifdef __USE_MALLOC
typedef malloc_alloc alloc; typedef malloc_alloc single_client_alloc;
# else ... typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc; typedef __default_alloc_template<false, 0> single_client_alloc; ... #endif
|
一级配置器实现
用malloc()
, free()
, realloc()
等C函数执行实际的内存配置、释放、重新配置,并模拟实现类似于C++ new-handler异常处理机制。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
|
template<int inst> class __malloc_alloc_template {
private: static void *oom_malloc(size_t); 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 (0 == result) result = oom_malloc(n); return result; }
static void deallocate(void* p, size_t ) { free(p); }
static void *reallocate(void* p, size_t , size_t new_sz) { void *result = realloc(p, new_sz); if (0 == result) result = 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; } };
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_malloc_handler)(); void* result; for (; ;) { my_malloc_handler = __malloc_alloc_oom_handler; if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; } (*my_malloc_handler)(); result = malloc(n); if (result) return result; } }
template<int inst> void* __malloc_alloc_template<inst>::oom_realloc(void* p, size_t n) { void(*my_malloc_handler)(); void* result; for (; ;) { my_malloc_handler = __malloc_alloc_oom_handler; if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; } (*my_malloc_handler)(); result = reallocate(p, n); if (result) { return result; } } }
typedef __malloc_alloc_template<0> malloc_alloc;
|
第二级配置器:__default_alloc_template
与第一级配置器区别:为避免太多小额区块造成内存碎片,多了一些机制。
SGI第二级配置做法:如果区块够大,> 128bytes,移交给第一级配置器处理;当区块 < 128bytes,则以内存池(memory pool)管理。
这种方法称为次配置(sub-allocation):每次配置一大块内存,并维护对应自由链表(free-list)。下次再有相同大小内存需求时,就直接从free-lists中取出。如果客户端归还小额区块,就由配置器回收到free-lists中。
简而言之,二级配置器负责内存配置、回收,会根据区块大小,选择自行配置,还是移交给一级配置器处理。
因此,可以知道二级配置器多了自由链表和内存池两个机制,专门为处理 <= 128bytes的内存申请而生。
free-lists
二级配置器的核心之一就是free-lists(自由链表),每个free-list代表一类空闲区块,大小从8,16,24,…,到128 (bytes),共16个。16个free-list的头结点,用一个数组free_list[16]
表示,下文称之为槽位。每个槽位指向的区块是一个链表,而该区块就是链表的第一个空闲块。
free-list的精髓就是联合体obj:
1 2 3 4 5
| union obj { union obj* free_list_link; char client_data[1]; };
|
一般情况下,我们用next 和 data的struct来描述链表节点,而obj用obj的union,这是为什么?
因为这样可以节省维护链表的指针空间。一个区块,在分配给客户端之前,首部大小为obj那部分可以看作一个指针free_list_link,用来串成链表;而分配给客户端之后,这部分无需当做指针,可以被客户按需使用;待客户归还区块时,首部大小为obj那部分又会被当做指针,用来串成链表,加入free list。
free_list_link所指向的内存区块大小,由链表头结点,即槽位所在free_list[]中的索引决定。而归还时,调用者会记录区块大小。因此,obj不需要额外存储区块大小。如下所示:
__default_alloc_template 的数据结构
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| enum { __ALIGN = 8 }; enum { __MAX_BYTES = 128 }; enum { __NFREELTISTS = __MAX_BYTES / __ALIGN };
template<bool threads, int inst> class __default_alloc_template { private: static size_t ROUND_UP(size_t bytes);
private: union obj { union obj* free_list_link; char client_data[1]; };
private: static obj* volatile free_list[__NFREELTISTS]; static size_t FREELIST_INDEX(size_t bytes); static void *refill(size_t n); 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) { } static void deallocate(void* p , size_t n) { } static void* reallocate(void* p, size_t old_sz, size_t new_sz); };
|
二级配置器的allocate()
源码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| static void * allocate(size_t n) { obj* volatile* my_free_list; obj* result;
if (n > (size_t)__MAX_BYTES) { return (malloc_alloc::allocate(n)); }
my_free_list = free_list + FREELIST_INDEX(n); result = *my_free_list;
if (result == 0) { void *r = refill(ROUND_UP(n)); return r; }
*my_free_list = result->free_list_link; return (result); }
|
二级配置器额度deallocate()
源码如下,就是把该obj
放在相应free list的第一个位置上。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| static void deallocate(void* p , size_t n) { obj* q = (obj*)p; obj* volatile *my_free_list;
if (n > (size_t)__MAX_BYTES) { malloc_alloc::deallocate(p, n); return; }
my_free_list = free_list + FREELIST_INDEX(n); q->free_list_link = *my_free_list; *my_free_list = q; }
|
refill函数重新填充free list
在allocate()
中,当发现合适的free list中并没有可用的空闲块时,就会调用refill()
为free list重新填充空闲空间。新空间由chunk_alloc()
完成,默认取自内存池。
refill()
默认向chunk_alloc()
申请nobjs=20个大小为n(假定n已经调整为8倍数)的(连续)内存空间,当然实际成功申请到多少个,需要根据实际情况决定,可通过nobjs传出值判断。可以肯定的是,如果有返回值(没有出现异常终止程序),那么至少会有一个大小为n的对象。
refill()
会得到一个连续空间,而把第一个大小n的对象返回给客户;至于剩余的空间,在按尺寸n找到合适的free list后,将剩余空间按链表形式加入free list。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
|
template<bool threads, int inst> void* __default_alloc_template<threads, inst>::refill(size_t n) { int nobjs = 20;
char* chunk = chunk_alloc(n, nobjs); obj* volatile *my_free_list; obj* result; obj *current_obj, *next_obj; int i;
if (1 == nobjs) return (chunk);
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 (nobjs - 1 == i) { current_obj->free_list_link = 0; break; } else { current_obj->free_list_link = next_obj; } }
return (result); }
|
我们看到这个refill()
函数首先调用了chunk_alloc()
函数,从内存池中申请20个大小为n
的区块(可能少于20个,因为内存池可能容量不足,但会分配至少1个obj
),并把其中第一个区块传给chunk
,另外的nobjs - 1
个区块再添加到free-list中。
内存池自身通过两个指针边界管理,start_free
~ end_free
;而heap_size
,表示总的向OS成功申请到的内存总量。需求的内存总量 total_bytes为size * nobjs
,内存池剩余空间bytes_left为 end_free - start_free
。
当内存池剩余空间 >= 需求内存总量时,直接从内存池划扣(移动start_free
边界)。
当内存池剩余空间不能完全满足需求量,但足够供应一个(含)以上的区块需求。
我们知道,客户(refill()
)通过chunk_alloc()
申请内存的时候,实际上只需要一个区块,但会默认申请20个区块。也就是说,实际上最少只供应一个也能满足需求。但我们还是让内存池尽量满足客户需求,分配尽量多的区块数nobjs = bytes_left / size
。这样,实际供应的总量为size*nobjs
。同样地,从内存池划扣空间需要移动start_free
边界。
当内存池剩余空间连一个区块都不能满足时,可能需要向OS申请内存(调用malloc()
)。
会不会出现严重的内存碎片问题?
不会的,因为之前用过的内存释放后会重新加入到free-list中,不会被free
。也就是说这种小空间(小于128bytes)不会造成内存碎片的问题。